반응형
📌강의 정리
투포인터 모르면 이중포문 쓸 것이다. 그러지 말자
이준포문이면 n^2알고리즘이 된다.
투포인터는 단일 포문으로 풀 수 있다.
포인터 변수는 lt,rt이다.
lt는 가만히 있고 rt만 더해가며 M인지를 확인해간다.
rt가 변하다 M을 넘으면 lt를 증가시켜 다시 확인하고
같아지면 다시 lt를 움직인다.
rt가 증가하든 lt가 증가하든 6인지는 확인을 해야한다.
이렇게 알고리즘을 탐색하다가 rt가 끝나면 탐색이 끝난 것이다.
rt는 for문돌릴때 기준으로 돌린다.
이제 코드로 알고리즘을 짜면 sum+=arr[rt]; 로 rt를 계속 더하게 한다.
이때 매순간 M과 같은지 if문을 통해서 짜준다.
sum-=arr[lt++];
if(sum===m) answer++; 으로 같은지 확인을 하고
while(sum≥m)을 통해서 반복문을 짜서 lt는 항상 빼가며
sum과m이 같은 answer를 ++해준다.
📌느낀점
솔직히 내가 푼 방법은 이중포문이기는 한데 그게
강사님의 for while과 크게 다른 것 같지는 않다..
하지만 강사님 풀이가 확실히 투포인터에 정석같은 느낌이다.
lt와rt 두개의 포인터가 움직이며 탐색을 진행한다.
이 문제가 투포인터의 대표문제라 하셨으니 꼭 잘 알아두어야 겠다.
(220615 +) 당연히 다르지, 드디어 과거의 나를 확실하게 이겼고 성장했다는 느낌이 든다. 근데 그 성장이 되게 미묘하다… 성장했다는 것에 중점을 두자.
//220615
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = 0;
let cnt = 0;
let lt = (rt = 0);
let sum = 0;
while (1) {
sum = 0;
//투포인터를 응용해 lt와 rt를 움직이며 그 안의 수를 더하고
for (let j = lt; j <= rt; j++) {
sum += arr[j];
}
//같으면 출력, rt 오른쪽으로
if (sum === m) {
//rt가 끝에 왔을때 더했는데 타겟넘버보다 같으면 반복을 끝낸다.
if (rt === arr.length - 1) break;
cnt++;
rt++;
//작으면 rt를 오른쪽으로
} else if (sum < m) {
//rt가 끝에 왔을때 더했는데 타겟넘버보다 작으면 반복을 끝낸다.
if (rt === arr.length - 1) break;
rt++;
//크면 lt를 오른쪽으로
} else if (sum > m) lt++;
}
answer = cnt;
return answer;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
</script>
</body>
</html>
//나의 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=0;
let n = arr.length;
let p = 0;
let cnt = 0;
for(let i=0;i<n;i++){
let res = 0;
for(let p=i;p<n;p++){
res+=arr[p];
if(res === m){
cnt++;
res = 0;
break;
}
if(res > m){
res = 0;
break;
}
}
}
answer = cnt;
return answer;
}
let a=[1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr){
let answer=0, lt=0, sum=0;
for(let rt=0; rt<arr.length; rt++){
sum+=arr[rt];
if(sum===m) answer++;
while(sum>=m){
sum-=arr[lt++];
if(sum===m) answer++;
}
}
return answer;
}
let a=[1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));
</script>
</body>
</html>
반응형
'JS 알고리즘 문제풀이 > 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)' 카테고리의 다른 글
| 6.학급 회장(Hash Map) (0) | 2022.06.18 |
|---|---|
| 5.최대 매출(Sliding Window) (0) | 2022.06.17 |
| 4.연속부분수열2(Two Pointers Algorithm) (0) | 2022.06.16 |
| 2.공통원소구하기(Two Pointers Algorithm) (0) | 2022.06.14 |
| 1.두 배열 합치기(Two Pointers Algorithm) (0) | 2022.06.13 |