📖 문제 해결 패턴(Problem Solving Patterns)

다음은 알고리즘 문제를 패턴화해 문제 해결에 도움을 줄 수 있는 패턴들이다.

• Frequency Counter
• Multiple Pointers
• Sliding Window
• Divide and Conquer
• Dynamic Programming
• Greedy Algorithms
• Backtracking
• ...

이 중 오늘 포스팅에서는 Multiple Pointers, 다중 포인터라고 강의에서 칭하는 패턴에 대해 이야기하겠다.

📌 다중 포인터 : Multiple Pointers

이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음, 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것이다.

예시를 살펴보자.

정렬된 정수형 배열을 인수로 받는 sumZero 함수를 작성한다. 이 함수는 합계가 0인 첫번째 쌍을 찾는다. 두 수를 더해 0이 되는 쌍을 배열로 리턴하고, 만약 그런 값이 없다면 undefined를 리턴한다. 이때 배열은 정렬되어 있다.

sumZero([-3,-2,-1,0,1,2,3]) // [-3,3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined

📌 Naive Solution

다중 포인터 패턴을 사용하지 않은 naive한 방법은 다음과 같다.

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}
//인덱스 i에서 i+1의 수를 계속 돌면서 합이 0이되는 수를 찾아 리턴하는 로직이다.

sumZero([-4,-3,-2,-1,0,1,2,5]) //[-2,2]

위 코드는 for문의 중첩으로 인해 시간복잡도 O(N^2), 공간복잡도 O(1)을 가진다.

📌 Refactored Solution

function sumZero(arr) {
    //좌, 우 양 끝의 인덱스를 이용한다
    let left = 0;
    let right = arr.length - 1;
    
    //right인덱스가 left인덱스보다 클 경우(두 인덱스가 만나지 않았을때까지)
    while (left < right) {
    	//양쪽의 값이 합해서 0인지 확인한다
        let sum = arr[left] + arr[right];
        //0이라면
        if (sum === 0) {
        //배열 리턴
            return [arr[left], arr[right]];
        //0보다 크면 오른쪽 인덱스를 감소시켜 하나 당겨옴
        //순서대로 정렬되어있으므로, 현재 오른쪽 인덱스와 합이 0이 되는 수가 있을 가능성이 없기 때문
        } else if (sum > 0) {
            right--;
        //마찬가지로 왼쪽 인덱스를 증가합
        } else {
            left++;
        }
    }
}

console.log(sumZero([-3, -2, -1, 0, 1, 2])); // [-3,3]
console.log(sumZero([-2, 0, 1, 3])); //undefined
console.log(sumZero([1, 2, 3])); // undefined

위 코드는 시간복잡도 O(N), 공간복잡도 O(1)을 가진다.

✏️ Multiple Pointers - countUniqueValues

다음 문제를 풀어보자.

정렬된 배열을 받고, 해당 배열에서 중복을 제거한 숫자들의 개수를 반환하는 countUniqueValues라는 함수를 작성한다. 인수로 들어오는 배열은 음수가 포함될 수 있지만 항상 정렬되어 있다. 이때 시간복잡도는 O(N), 공간복잡도는 O(N)이다.

countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4

function countUniqueValues(arr){
	//만약 빈 배열이라면 0을 반환 
    if(arr.length === 0){
        return 0;
    }
    
    let firstIndex = 0;
    for(let secondIndex =1; secondIndex<arr.length; secondIndex++){
    	//첫번째 인덱스의 값과 두번째 인덱스의 값이 같지 않으면
        if(arr[firstIndex] !== arr[secondIndex]){
        	//첫번째 인덱스를 증가시켜주고
            firstIndex++;
			//첫번째 인덱스에 두번째 인덱스값을 넣어준다(그 뒤 두번째 인덱스는 반복문을 통해 증가되어 같은 과정을 반복)
            arr[firstIndex] = arr[secondIndex];
        }
    }
    //중복을 거르고 남은 숫자는 인덱스의 값에 +1을 한 것과 같음(인덱스가 0부터 시작하므로)
    return firstIndex+1;
}

강의의 솔루션과 동일하게 문제를 해결할 수 있었다.

✏️ Multiple Pointers - areThereDuplicates

앞서 '빈도 수 세기' 패턴에서 해결한 areThereDuplicates 문제도 다중 포인터 패턴으로 해결할 수 있다.

areThereDuplicates라는 함수를 작성해라. 이때 인수의 개수는 정해지지 않는다. 받은 인수들 중에 중복된 값이 있는지 판별해라.
시간,공간 복잡도는 O(n)이어야 한다.

areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
areThereDuplicates('a', 'b', 'c', 'a') // true

function areThereDuplicates(...arr) {
    let firstIndex = 0;
    //배열을 정렬해준다.
    arr.sort();
    //두번째 인덱스의 증가를 반복한다 이때 첫번째 인덱스와 두번째인덱스의 값이 같으면 true를 반환한다.
    //같지 않으면 firstIndex를 늘려주고, for문이 끝날때까지 리턴되지 않았으면 false를 리턴해준다.
    for(let secondIndex=1; secondIndex<arr.length; secondIndex++ ){
        if(arr[firstIndex] === arr[secondIndex]){
            return true;
        }
        firstIndex++;
    }
    
    return false;
}

✏️ Multiple Pointers - averagePair

정수형 배열과 평균 목표를 인수로 받는 averagePair라는 함수를 작성한다. 인수로 받은 배열에 존재하는 값의 쌍의 평균이 인수로 받은 평균 목표와 같은 것이 있는지를 확인한다. 시간복잡도는 O(N), 공간복잡도는 O(1)이다.

function averagePair(arr, avg){
	//빈 배열이면 false를 반환한다.
    if(arr.length === 0){
        return false;
    }
    
    //첫번째 인덱스와 두번째 인덱스를 배열 양 끝의 인덱스로 초기화한다.
    let firstIndex = 0;
    let secondIndex = arr.length-1;
    
    //두번째 인덱스가 첫번째 인덱스보다 클때동안 반복한다.
    while(firstIndex<secondIndex){
    	//만약 각 인덱스에 해당하는 배열값의 평균값이 avg와 같으면 true를 리턴한다.
        if((arr[firstIndex] + arr[secondIndex])/2 === avg){
            return true;
         //각 인덱스에 해당하는 배열값의 평균값이 avg보다 작으면
         //첫번째 인덱스를 기준으로할때, 두번째 인덱스가 어떠한 값이 되도 평균치와 같을 수 없으므로, firstIndex를 증가시켜준다.
        }else if((arr[firstIndex] + arr[secondIndex])/2 < avg){
            firstIndex++;
        //반대라면 secondIndex를 감소시킨다.
        }else{
            secondIndex--;
        }
    }
    return false;
}

✏️ Multiple Pointers - isSubsequence

isSubsequence라는 함수를 작성한다. 이 함수는 두 개의 문자열을 인수로 받고, 첫 번째 문자열의 문자가 두 번째 문자열에 연속적으로 존재하는지를 판단해 반환한다. 즉, 첫 번째 문자열의 문자가 순서를 변경하지 않고 두 번째 문자열의 어딘가에 나타나는지 여부를 확인해야 한다. 솔루션은 적어도 시간복잡도 O(N+M), 공간복잡도 O(1)를 만족해야 한다.

isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)

function isSubsequence(string1, string2) {
	//각 string1, string2를 순회하는 인덱스
    let firstIndex = 0;
    let secondIndex = 0;
	
    for(secondIndex; secondIndex<string2.length ;secondIndex++){
    	//만약 string1과 string2의 글자가 같으면 firstIndex를 증가시켜 string1의 다음 글자로 이동
        if(string1[firstIndex] === string2[secondIndex]){
            firstIndex++;
        }
        //만약 firstIndex가 string1의 길이와 같으면 끝까지 조회했다는 뜻이므로 true반환
        if(firstIndex === string1.length){
            return true;
        }
    }
    return false;

}

💗 Multiple Pointers Solutions

강의에서 제시한 솔루션은 다음과 같다.

💗 areThereDuplicates solution

function areThereDuplicates(...args) {
	//배열을 정렬해준다.
 	args.sort((a,b) => a > b);
 	//첫번째 인덱스와 두번째 인덱스에 값을 초기화해준다.
 	let start = 0;
    let next = 1;
    
    //두번째 인덱스가 배열의 길이보다 적을때까지(배열의 끝에 도달하기 전까지) 반복한다.
    while(next < args.length){
    	//만약 배열의 첫번째 인덱스가 두번째인덱스값과 같으면 true를 리턴해준다.
    	if(args[start] === args[next]){
        	return true
    	}
    //그리고 첫번째 인덱스와 두번째 인덱스 값을 증가시켜준다.
    start++
    next++
  }
  //만약 while이 끝난후에도 리턴되지 않았다면 같은것이 없었던 것이므로 false리턴
  return false
}

function areThereDuplicates() {
	//set으로 배열을 받아서 사이즈가 배열의 길이와 같은지 비교한다.(Set은 중복을 제거함)
  return new Set(arguments).size !== arguments.length;
}

💗 averagePair solution

while문과 for문의 차이를 제외하고는 나의 풀이랑 같다.

function averagePair(arr, num){
  let start = 0
  let end = arr.length-1;
  while(start < end){
    let avg = (arr[start]+arr[end]) / 2 
    if(avg === num) return true;
    else if(avg < num) start++
    else end--
  }
  return false;
}

💗 isSubsequence solution - 반복

while문과 for문의 차이를 제외하고는 나의 풀이랑 같다.

function isSubsequence(str1, str2) {
  var i = 0;
  var j = 0;
  if (!str1) return true;
  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }
  return false;
}

💗 isSubsequence solution - 재귀

function isSubsequence(str1, str2) {
   //만약 str1의 길이가 0이면 true
  if(str1.length === 0) return true
  //만약 str2의 길이가 0이면 false
  if(str2.length === 0) return false
  //만약 str2와 str1의 첫 글자가 같으면 재귀함수 호출(이때 첫 문자를 잘라냄)
  if(str2[0] === str1[0]) return isSubsequence(str1.slice(1), str2.slice(1))  
  //같지 않으면 str2에서 첫글자를 잘라낸 문자열과 str1를 인수로하는 재귀함수 호출 
  return isSubsequence(str1, str2.slice(1))
}

📘 참고 자료
https://www.udemy.com/course/best-javascript-data-structures/