[알고리즘] - 슬라이딩 윈도우, Two pointers

어제 데일리 퀴즈 스택 관련 리뷰

최솟값 만들기 문제에서 스택을 이용하면 원래의 순서를 유지하면서 오름차순 정렬!
ex) 132456 의 원소를 각각 차례로 넣엇을 때, 1 -> 3 -> 2에서 3을 제외하고 2를 넣음 --> O(n^2)을 O(n)으로 할 때 좋음!
반대로 자기 보다 작은 값을 빼게되면 순서는 유지하면서 내림차순 정렬!

2322113 을 넣을 때 2 다음 3이 들어갈때 앞의 값보다 작으므로 k를 감소시키고 다음 다시 2를 넣을때 앞의 것과 같은 경우 그냥 넣어주고 1을 넣을 때, 스택안에 있는 값들과 비교를 하면서 자기보다 크므로 k를 감소시키면서 스택안의 값들을 지워준다.

123456같이 쭉 증가한 경우에는 스택은 오름차순을 유지하고 있기 때문에 2개를 뒤에서 k만큼 제거해준다.

function solution(num, k) {
    let answer;
    let stack = [];
    for(let x of num.toString()) {
        while(k>0 && stack.length && stack[stack.length-1] > x){
            stack.pop();
            k--;
        }
        stack.push(x);
    }
    answer = stack.join("");
    answer = answer.substring(0, answer.length-k);
    if(answer.length===0) return 0;
    console.log(answer);
    return Number(answer);
}

console.log(solution(200200, 1));

강사님 퀴즈 코드
// O(n^2)을 O(n)으로 품 --> for문 안에 while문이 있다고해서 무조건 O(n^2)이 아님!
// while이 실제적으로 얼마나 도는지를 확인해야함! n x n이 아니라 스택에 있는 것만 비교하는 것이어서 n^2 아닌듯
// 프로그래머스 큰 수만들기, 주식가격
// 백준의 탑 풀고 주식가격 푸는것이 좋을듯

---

아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.

[슬라이딩윈도우, two pointers Algorithm]

최대 매출

N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 합 중 최대값을 구하여라
[12, 15, 11, 20, 25, 10, 20 19, 13, 15], 3 이렇게 주어지면 56이 나와야함

📌 내가 푼 방법

function solution(nums, k) {
    let answer = 0;
    let start = 0;
    let end = 0;
    let sum = 0;

    while(end < nums.length) {
        if(end-start === k) {
            sum -= nums[start];
            start++;
        }
        sum += nums[end];
        answer = Math.max(sum, answer);
        end++;
    }
    return answer;
}

const nums = [12, 34, 56, 72, 93, 121, 33, 11, 23, 52];
const k = 4;

console.log(solution(nums, k));

end와 start를 비교해 가면서 k만큼 차이날 때, 앞의 start를 증가시키기 위해 sum에서 빼주고 다시 시작한다

📌 강사님 방법

function solution(nums, k) {
    let answer = 0;
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    for (let i = k; i < nums.length; i++) {
        sum += (nums[i] - nums[i - k]);
        answer = Math.max(answer, sum);
    }
    return answer;
}

const nums = [12, 34, 56, 72, 93, 121, 33, 11, 23, 52];
const k = 4;

console.log(solution(nums, k));

미리 값을 넣어두고 그 뒤부터 돌면서 최대값을 answer에 담아서 반환!

---

매출액의 종류

N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를 모두 구하되 예를들어 연속된 3일간 기록이 [10, 10, 11] 일땐 매출액의 종류는 2이다.

📌 내가 푼 방법

function solution(nums, k) {
    let answer = [];
    let tempArr = [];
    let end = 0;
    let same = 0;

    while(end < nums.length) {
        tempArr.push(nums[end]);
        if(tempArr.length === k+1){
            same = tempArr.length - new Set(tempArr).size;
            answer.push(tempArr.length - same);
            tempArr.shift();
        }
        end++;
    }

    return answer;
}

const nums = [1, 2, 3, 2, 2, 3, 3, 3, 3, 2];
const k =  3;

console.log(solution(nums, k));

커리어 OT과제를 하고나서 풀다가 시간이 지나 여기서부터 풀지 못했다..
아마 실행안될듯..

📌 강사님 방법

function solution(nums, k) {
    let answer = [];
    let nH = new Map();

    for(let i = 0; i<k-1; i++) {
        nH.set(nums[i], nH.get(nums[i]) +1 || 1);
    }
    let lt = 0;
    for(let i = k-1; i<nums.length; i++) {
        nH.set(nums[i], nH.get(nums[i]) + 1 || 1);
        answer.push(nH.size);
        nH.set(nums[lt], nH.get(nums[lt]) - 1);
        if(nH.get(nums[lt]) === 0) {
            nH.delete(nums[lt]);
        }
        lt++
    }

    return answer;
}

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

마찬가지로 윈도우의 길이에서 하나만큼 뺀 값을 Map에 넣어두고 시작해서 for문을 돌면서 map과 size를 이용해서 중복되는 것을 거르고 answer에 push한다. 만약 키의 값이 0이면 그 키는 이미 슬라이딩 윈도우에 없는 것이므로 delete로 제거해준다

---

연속 부분수열 1 // two point알고리즘의 대표문제

N개의 수로 이루어진 수열이 주어지면 합이 M이 되는 연속 부분수열의 개수를 반환하여라

📌 내가 푼 방법

시간이 안되어서 풀어보지 못함..

📌 강사님 방법

function solution(nums, m) {
    let answer = 0;
    let lt = 0;
    let sum = 0;

    for (let rt = 0; rt < nums.length; rt++) {
        sum += nums[rt];
        if (sum === m) {
            answer++;
        }
        while (sum > m) { // sum에서 lt를 이용해 빼주어도 m보다 클 수 있으므로 while문으로 m보다 작거나 같아질 때 까지 확인!
            sum -= nums[lt]; // lt를 빼줬으니 lt 증가시켜야함
            lt++;
            if (sum === m) { // sum값이 lt에 의해 변했으니 확인시켜야함.
                answer++;
            }
        }
    }
    return answer;
}


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

lt를 0으로 초기화시킨 후 for문을 rt = 0으로 시작해서 쭉 돈다. for문 안에 sum이라는 변수를 만들어 그곳에 rt가 돌면서 sum값을 증가시킴 만약 sum값이 m보다 크게 되면 sum이 m보다 작거나 같을때까지 lt를 이용해 빼주어야함 --> while문 사용!

---

연속 부분수열 2

N개의 수로 이뤄진 수열이 주어지면 합이 M이 되는 경우가 몇 번 있는 지 구하여라

📌 내가 푼 방법

시간이 안되어서 풀어보지 못함..

📌 강사님 방법

// 연속 부분수열 2

function solution(nums, m) {
    let answer = 0;
    let nH = new Map();
    let sum = 0;
    
    for(let i = 0; i< nums.length; i++)
    {
        sum += nums[i];
        if(sum === m) { // sum이 target값인지 확인하고 answer증가
            answer++;
        }
        if(nH.has(sum-m)) answer+=nH.get(sum-m);
        nH.set(sum, nH.get(sum)+1 || 1); // map에 sum을 key로 값을 계속해서 넣어줌
    }
    return answer;
}


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

위의 문제와 비슷해보이지만 입력값에 0과 음수가 들어가면 완전히 달라짐.
위의 방법으로 풀 수 없고 다른 식으로 풀어야함
why? -> 3을 만들으라고 할때 {3, -3, 0, 3} 도 3이 될 수 있음!
해시맵을 사용해서 푼다!
sum 현재부터 최종까지의 누적합을 기록하는 변수
nH변수에 sum을 키로하는 값을 넣어줌.
(sum-m)의 의미를 잘 이해하는 것이 중요!

---

연속 부분수열 3

N개의 수로 이뤄진 수열이 주어지면 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하여라

📌 내가 푼 방법

시간이 안되어서 풀어보지 못함..

📌 강사님 방법

function solution(nums, m) {
    let answer = 0;
    let lt = 0;
    let sum = 0;
    for(let rt = 0; rt < nums.length; rt++) {
        sum += nums[rt];
        while(sum > m) {
            sum -= nums[lt];
            lt++;
        }
        answer += (rt-lt+1); // 그냥 계속 해줌. 이 식은 rt가 마지막 항으로 하는 연속 부분수열
    }

    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)); // 1

중요부분은 answer += (rt-lt+1)이다. (lt와 rt로 만들 수 있는 m이하의 수들을 세주는 식임)

---

연속된 자연수의 합

양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법을 구하여라

📌 내가 푼 방법

시간이 안되어서 풀어보지 못함..

📌 강사님 방법

function solution(n) {
    let answer = 0;
    let lt = 0;
    let sum = 0;
    let m = parseInt(n / 2) + 1;
    let nums = Array.from({ length: m }, (v, i) => i + 1);

    for (let rt = 0; rt < m; rt++) {
        sum += nums[rt];
        if (sum === n) answer++;
        while (sum > n) {
            sum -= nums[lt++];
            if (sum === n) answer++;
        }
    }
    return answer;
}

console.log(solution(15)); // 3
console.log(solution(45678)); // 7
console.log(solution(98765)); // 3


수학적인 방법으로 다음의 방법도 있다.

function solution(n) {
    let answer = 0;
    let cnt = 1;
    n--;
    while (n > 0) {
        cnt++;
        n -= cnt;
        if (n % cnt == 0) answer++;
    }
    return answer;
}

한번 나누어 준 후 배열로 만들어 전과같이 lt, rt 를 통해 증가시키면서 비교를 해본다.

---

모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하여라

📌 내가 푼 방법

시간이 안되어서 풀어보지 못함..

📌 강사님 방법

function solution(s, t) {
    let answer = 0;
    let sH = new Map();

    for (let x of t) {
        sH.set(x, sH.get(x) - 1 || -1); // 중복되는것이 있는 경우 그 문자열 부분에 -1을 더해주어야함
    }

    let len = t.length - 1
    for (let i = 0; i < len; i++) {
        if (sH.get(s[i]) === -1) sH.delete(s[i]);
        else sH.set(s[i], sH.get(s[i]) + 1 || 1);
    }
    let lt = 0;
    for (let rt = len; rt < s.length; rt++) {
        if (sH.get(s[rt]) === -1) sH.delete(s[rt]);
        else sH.set(s[rt], sH.get(s[rt]) + 1 || 1);
        if (sH.size === 0) answer++;
        if (sH.get(s[lt]) === 1) sH.delete(s[lt]);
        else sH.set(s[lt], sH.get(s[lt]) - 1 || -1);
        lt++;
    }
    return answer;
}

console.log(solution("bacacbcba", "abc")); // 3
console.log(solution("bacaAacba", "abc")); // 3

map을 이용하여 map의 사이즈가 0일 때 아나그램이다.
0으로 걸러내면 문제가 생길 수 있다.
-1 값을 갖는 키 먼저 제거를 해주기