주벨로퍼의 개발 공부

1. 투포인터 알고리즘이란?

  1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작하면서 원하는 결과를 얻는 알고리즘이다!

2. 대표 문제 1 - 공통원소 구하기

  두 개의 집합 A,B 의 공통 원소를 구해서 오름차순으로 출력하는 함수를 작성하시오.

function getCommonNums(a, b) {
	let answer = [];
    a.sort();
    b.sort();
    // a, b 배열을 오름차순으로 정렬
    
    let p1 = 0;
    let p2 = 0;
    // 두 개의 포인터를 선언 및 초기값 0 할당
    
    while (p1 < a.length && p2 < b.length) {
    	if (a[p1] === b[p2]) {
        	answer.push(a[p1++]);
            p2++;
        } else if (a[p1] < b[p2]) {
        	p1++;
        } else {
        	p2++;
        }
    }
    return answer;
}

3. 대표 문제 2 - 연속 부분수열 1

  n개의 수로 이루어진 수열이 있다. 이 수열에서 연속 부분수열의 합이 특정숫자 m이 되는 경우가 몇 번 있는지 구하는 함수를 작성하자.

function solution(arr, m) {
	let answer = 0, lt = 0, sum = 0;
    for(let rt = 0; rt < arr.length; rt++){
    	sum += arr[rt];
        // 포인터 rt를 하나씩 증가시키면서 sum에 누적한다
       	if(sum === m) answer++;
        // 만약 sum이 목표 값인 m과 같으면 answer에 1을 더한다
        while(sum >= m){
       		sum -= arr[lt++];
            // sum이 m보다 크거나 같은 경우 포인터 lt가 가리키고 있는 값을 빼고 lt를 1증가
            // 해당 과정은 sum이 m보다 다시 작아질 때까지 수행되어야함
            // 이미 sum이 m보다 큰데 rt를 더하는 것은 의미가 업기 때문!
            if(sum === m) answer++;
            // lt가 가리키는 값을 뺄때도 값 비교는 꼭 해줘야함!
            // 부분수열의 합이 목표 값과 같은지 아닌지를 구하는 것이기 때문에
        }
    }        
    return answer;
}

4. 대표 문제 3 - 연속 부분수열 2

  위 문제의 변형 문제이다. n개의 수로 이루어진 수열에서 연속부분수열의 합이 특정숫자 m이하가 되는 경우는 몇 번인가?

function solution(arr, m) {
	let answer = 0, sum = 0, lt = 0;
    for (let rt = 0; rt < arr.length; rt++) {
    	sum += arr[rt];
        // 위 문제와 마찬가지로 rt를 하나씩 증가시키면서 rt가 가리키는 값을 sum에 더한다.
        while (sum > m) {
        	sum -= arr[lt++];
            // sum이 m보다 커지는 순간 sum이 m이하가 될 때까지 lt가 가리키는 값을 빼고 lt를 1씩 증가
        }
        answer += (rt - lt + 1);
        // rt - lt + 1의 의미는?
        // sum에 새롭게 추가된 arr[rt]를 포함하는 연속 부분수열의 개수!
        // 예를 들어 arr = [1, 3, 1, 2, 3] 이라고 하자
        // rt = 0 일땐 첫 번째 원소를 포함하는 부분수열은 {1} 이므로 +1
        // rt = 1 일땐 두 번째 원소를 포함하는 부분수열은 {3}, {1, 3} 이므로 +2
        // rt = 2 일땐 세 번째 원소를 포함하는 부분수열은 {1}, {3, 1}, {1, 3, 1} 이므로 +3
    }               
    return answer;
}