티스토리 뷰

Algorithm/JavaScript 알고리즘

[JS - 알고리즘] 03. 투포인터 알고리즘(슬라이딩 윈도우)

MinsoftK 2021. 10. 11. 04:11
728x90
반응형

투 포인터 알고리즘, 슬라이싱 윈도우

이전 문자열과 해싱이나 1차원 배열 같은 경우 구현 문제들이었다.(물론 효율적으로 풀어야 되는 문제들도 있었다.) 현재 투 포인터 알고리즘 카테고리를 학습하면서 수학적인 사고가 필요한 부분들이 많아졌다. 이전엔 문제에 주어진대로 풀다 보니 시간 복잡도를 생각하지 못했다. O(N3)까지 쓰면서 문제를 해결에만 집중했다. 하지만 알고리즘 스터디와 공부를 진행하다 보니 어려운 문제를 굉장히 수학적인 방법으로 간단하게 푸는 방식을 보면서, 알고리즘이 왜 중요한지 알 수 있었다. 이제는 O(N3)을 어떻게 O(N)으로 풀어낼 것인가를 조금이나마 고민하게 됐다.

  • N의 조건이 100,000 정도가 넘어갈 때, 시간복잡도가 N2이 되면 문제가 생길 수도 있다. (참고)
  • 따라서 더욱 효율적으로 문제를 해결하기 위해서 사용하는 방법들이 있다. 슬라이싱 윈도우란?
  • 투 포인터와 슬라이싱 윈도우는 구간을 훑으면서 지나간다는 공통점이 있으나, 슬라이딩 윈도우는 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있습니다.

1. 최대 매출

function solution(nums, k) {
    let max = 0;
    let sum = 0;
    let start = 0,
        end = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        end++;
        
        // 만약 end, start 거리가 k 보다 커지면
        if (end - start > k) {
            // start의 값을 빼주고 idx ++
            sum -= nums[start];
            start++;
            max = Math.max(max, sum);
        }
    }
    return max;
}

console.log(solution([12, 15, 11, 20, 25, 10, 20, 19, 13, 15], 3));
console.log(solution([1, 2, 3, 5, 6, 7, 1, 3, 9], 5));
console.log(solution([12, 34, 56, 72, 93, 121, 33, 11, 23, 52], 4));

2. 매출액의 종류

  • 첫 번째 방법
function solution(nums, k) {
    let answer = [];
    let arr = [];
    let start = 0,
        end = 0;
    let max = 0;
    for (let i = 0; i < nums.length; i++) {
        arr.push(nums[i]);
        end++;
        if (end - start >= k && start <= nums.length - k) {
            let set = new Set();
            for (let x of arr) {
                set.add(x);
            }
            answer.push(set.size);
            arr = arr.slice(1, arr.length);
            start++;
        }
    }
    return answer;
}

console.log(solution([20, 12, 20, 10, 23, 17, 10], 4));
console.log(solution([1, 2, 3, 2, 2, 3, 3, 3, 3, 2], 3));
  • 2번째 방법
function solution2(nums, k) {
    let answer = [];
    let nh = new Map();
    let len = nums.length;
    for (let i = 0; i < k - 1; i++) {
        nh.set(nums[i], (nh.get(nums[i]) || 0) + 1);
    }

    let left = 0;
    for (let right = k - 1; right < nums.length; right++) {
        //k 개수에 맞게 right idx값 해시에 입력
        nh.set(nums[right], (nh.get(nums[i]) || 0) + 1);
        //size를 answer에 넣는다. 중복되지 않는다.
        answer.push(nh.size);
        //left idx 값을 해쉬에서 빼준다.
        nh.set(nums[left], nh.get(nums[left]) - 1);
        //만약 빼고 나서 val 값이 0이라면 해시에서 제거한다.
        if (nh.get(nums[left]) === 0) nh.delete(nums[left]);
        left++;
    }
    return answer;
}
console.log(solution([20, 12, 20, 10, 23, 17, 10], 4));
console.log(solution([1, 2, 3, 2, 2, 3, 3, 3, 3, 2], 3));

3. 연속 부분 수열-1

  • 내 풀이
function solution(nums, m) {
    let start = 0, end=0,
        sum = 0,
        answer = 0;
    while (start <= end && end <= nums.length) {
        if (sum === k) {
            cnt++;
            sum -= nums[start];
            start++;
        } else if (sum > k && start <= end) {
            // 만약 1 1 1 3 100 경우?
            //앞에 원소 빼준다.
            sum -= nums[start];
            start++;
        } else {
            //뒤에 원소 추가 해준다.
            sum += nums[end];
            end++;
        }
    }
    return answer;
}

console.log(solution([1, 2, 1, 3, 1, 1, 1, 2], 6));
console.log(solution([1, 1, 1, 1, 1, 1], 3));
console.log(solution([1, 2, 1, 2, 1, 2, 1], 3));

 

  •  풀이
    • for문을 이용해 right를 돌리는 방식을 사용하자.
function solution(nums, m) {
    let left = 0,
        sum = 0,
        answer = 0;

    for (let right = 0; right < nums.length; right++) {
        // 0부터 시작하므로 right idx를 이용해 sum에 더해준다.
        sum += nums[right];
        // sum 값이 m 보다 커졌을 때
        while (sum > m) {
            //left idx 값을 빼주고, +1 증가
            sum -= nums[left++];
        }
        // 만약 sum이 m 일때, answer 증가
        if (sum === m) answer++;
    }
    return answer;
}

console.log(solution([1, 2, 1, 3, 1, 1, 1, 2], 6));
console.log(solution([1, 1, 1, 1, 1, 1], 3));
console.log(solution([1, 2, 1, 2, 1, 2, 1], 3));

 

4. 연속 부분 수열-2

  • 가장 어려웠던 문제. 정확한 이해를 바탕으로 다른 곳에서도 사용할 줄 알아야 한다.
  • sum에 nums[i]를 차례대로 누적해나간다. 그러다 i번째에서 만약 (sum-m)의 key값이 존재한다면, key의 value만큼 m=3을 만드는 방법이, +nums[i]를 한 부분에도 value만큼 존재한다는 의미이다.
  • 즉 m=3 인 경우, for문을 돌면서 sum = 6 이 됐을 때, (key=3, value=2)가 해시에 있다면 (sum-m = 3)을 만족한다. 해시의 3인 key값을 조회하고 value 값인 2를 추가로 더해준다. 이는 +nums[i]를 sum에 더했을 때 일어난 경우다. 따라서 반대쪽으로도 m=3을 만들어주는 2가지 방법이 존재한다는 의미이다.
function solution(nums, m) {
    let answer = 0,
        sum = 0;

    let hash = new Map();
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum === m) answer++;
        
        // 만약 sum - m에 key를 가진다면, (sum - m) key의 value만큼 
        // sum에서도 m을 만드는 방법이 존재한다는 의미. 이 부분이 생각하기 어렵다.
        if (hash.has(sum - m)) answer += hash.get(sum - m);
        hash.set(sum, (hash.get(sum) || 0) + 1);
    }
    return answer;
}

console.log(solution([1, 2, 3, -3, 1, 2], 3));
console.log(solution([-1, 0, 1], 0));
console.log(solution([-1, -1, -1, 1], 0));

 

5. 연속 부분 수열 3

  • 연속된 부분 수열이기 때문에 right - left + 1 을 쓰게 된다면, 해당 숫자를 포함한 수열까지 포함하게 된다.
function solution(nums, m) {
    let left = 0,
        sum = 0,
        answer = 0;

    for (let right = 0; right < nums.length; right++) {
        // sum에 right idx 값 더해주며 +1 증가시킨다.
        sum += nums[right];
        // sum이 m보다 커지면 left idx값 빼주고, 증가시킨다.
        while (sum > m) {
            sum -= nums[left++];
        }
        // 현재 sum <= m을 만족하는 상태, 그러면 nums[right]를 더했을 때 만족한다는 의미다.
        // 이는 nums[right] 값도 m보다 작다는 의미이고, 현재까지의 sum도 m보다 작다는 의미이다.
        // 따라서 아래의 식이 만족하게 된다. 연속부분수열이라 가능한 부분
        answer += right - left + 1;
    }
    return answer;
}

console.log(solution([1, 3, 1, 2, 3], 5)); //10
console.log(solution([1, 1, 1, 1, 1, 1], 3)); //15
console.log(solution([1, 1, 2, 2, 1, 2, 1, 3, 2], 5)); //22

 

6. 연속된 자연수의 합

  • 첫 번째 방법
function solution(num) {
    let sum = 0,
        answer = 0,
        len = 0;

    // 나누기를 했을때 소수점 없애기 위해 parseInt를 사용.
    len = parseInt(num / 2) + 1;
    let arr = [];

    // 1번 idx부터 1을 입력해준다.
    for (let i = 1; i <= len; i++) {
        arr[i] = i;
    }

    // 1부터 시작
    let left = 1;
    for (let right = 1; right <= len; right++) {
        sum += arr[right];

        // 만약 sum이 num보다 커졌을때 left값 빼주고 인덱스 증가시킨다.
        while (sum > num) {
            sum -= arr[left++];
        }

        // num과 sum이 같다면 answer++ 
        if (sum === num) {
            answer++;
        }
    }

    return answer;
}

console.log(solution(15));
console.log(solution(45678));
console.log(solution(98765));
  • 2번째 방법

개인적으로 알고리즘을 학습하면서 연속 부분 수열 2번 다음으로 가장 수학적인 사고가 반영되지 않았나 싶다. N을 표현하는 가짓수를 표현하기 위해 연속된 숫자 1, 2를 먼저 뽑았다면 cnt=2이다. 그다음 N에서 cnt를 뺀다. 그러면 N - (1 + 2) 과 같다.

다음 입력된 숫자의 개수 cnt = 2 나누었을 때 나누어 떨어진다면, 연속된 숫자 1, 2가 해당 N- (1 + 2)를 나눠가질 수 있다. 따라서 N= 15일 때 연속된 숫자에 N- (1 + 2) / 2 = 6이다.

그러면 1, 2에 각각 6을 더한다면 7 + 8 = 15 가 된다. 이런 방식으로 다음과 같이 짤 수 있다.

function solution2(n) {
    let answer = 0;

    // 1부터 시작한다. cnt = 1
    cnt = 1;
    // 1부터 시작하기에 N에서 1을 먼저 빼준다.
    n--;

    // n이 0보다 클때만 
    while (n > 0) {
        // cnt가 2부터 시작한다.
        cnt++;

        // 이미 1은 빼져 있는 상태
        // 따라서 cnt = 2인 경우, n에서 cnt를 빼준다.
        n -= cnt;
        // 나누어 떨어진다면 1, 2가 N-(1+2)를 나눠가질 수 있다.
        if (n % cnt == 0) answer++;
    }
    return answer;
}
console.log(solution(15));
console.log(solution(45678));
console.log(solution(98765));

 

7. 모든 아나그램 찾기

  • left는 이제 비교하지 않으므로 s[left] key의 value 값을 1 감소시킨다. 이 부분이 이해하기 힘들었다. 해시의 응용문제.
function solution(s, m) {
    let answer = 0;
    let hash = new Map();

    // 부분 문자열을 hash에 -1로 저장하기
    // 슬라이딩 윈도우를 이용하여 아나그램을 찾는다.
    for (let x of m) {
        hash.set(x, (hash.get(x) || 0) - 1);
    }

    /* 부분 문자열의 길이 - 1을 해시에 넣는다.(이땐 value를 +1로 set을 한다.) 
    동작 후, value가 0이 되는 key값은 제거해준다.
    key의 vlaue가 0인 경우는 아나그램 조건인 부분 문자열 하나를 충족했다는 의미이다.
    */
    let len = m.length - 1;
    for (let i = 0; i < len; i++) {
        //  1~(비교할 문자열의 길이 -1) 해시에 등록
        hash.set(s[i], (hash.get(s[i]) || 0) + 1);
        if (hash.get(s[i]) === 0) hash.delete(s[i]);
    }

    /* 3번째 문자를 추가했을 때, 아나그램을 만족했다면 모든 해시 key의 value가 0이 된다.
    size=0인 경우, 아나그램 부분 문자열 개수 추가를 해준다.
    */
    let left = 0;
    for (let right = len; right < s.length; right++) {
        // 부분문자열 마지막 개수를 해시에 등록
        hash.set(s[right], (hash.get(s[right]) || 0) + 1);
        // 만약 해시의 value가 0이 되었다면, 해시에서 삭제해준다.
        // 삭제해주는 이유는 0도 size에 포함되기 때문에 1로 카운트 된다. size가 0일때, 아나그램을 만족한다.
        if (hash.get(s[right]) === 0) hash.delete(s[right]);
        if (hash.size === 0) answer++;

        // left는 이제 비교하지 않으므로 s[left] key의 value 값을 1 감소시킨다.         
        hash.set(s[left], (hash.get(s[left]) || 0) - 1);
        if (hash.get(s[left]) === 0) hash.delete(s[left]);
        left++;
    }
    return answer;
}

console.log(solution('bacacbcba', 'abc'));
console.log(solution('bacaAacba', 'abc'));
728x90
반응형
저작자표시 비영리

'Algorithm > JavaScript 알고리즘' 카테고리의 다른 글

[JS - 알고리즘] 02. 1차원 배열  (0) 2021.10.10
[JS - 알고리즘] 01. 문자열 해싱  (0) 2021.10.08
댓글