javascript 코딩테스트 - 다중 포인터

다중 포인터는 문자열, 배열 등과 같이 인덱스가 있는 자료구조에서 포인터를 여러개 두어 비교, 연산 등의 알고리즘을 수행하게 된다.

 

문제1

 

Write a function called averagePair. Given a sorted array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target average. There may be more than one pair that matches the average target.

 

averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) // true
averagePair([-1,0,3,4,5,6], 4.1) // false
averagePair([],4) // false

 

정렬된 숫자 배열과 평균값을 받고 평균값을 가지는 순서쌍이 배열 안에 있는지 없는지 확인하는 알고리즘을 구해보는 문제이다.

 

처음 든 생각

1. 배열이 이미 정렬되어있다는 거를 어떻게 쓸까.

2. 포인터를 양 끝으로 설정한 후 맞는 거를 찾아나가는 방식으로 해야겠다.

3. 특이상황에 대한 예외 처리를 앞에서 미리 해놓자.

function averagePair(arr, avg){
  // 양쪽 끝 포인터
  let i = 0
  let j = arr.length - 1 
  
  // 예외 처리
  if(arr.length<=1){
      return false
  }
  
  // 평균값과 비교하여 크면 큰 수를 줄이고 작으면 작은 수 키우고 큰 수는 다시 처음부터
  while(i<j){
      let sum = arr[i] + arr[j]
      if(sum === avg * 2){
          return true
      }
      if(sum >avg*2){
          j--
      } else {
          i++
          j=arr.length-1
      }
  }
  return false
}

평균값과 비교하여 작은 경우에 대해서 조금 헷갈렸다.

작으면 값을 키우면 되는데 두 개의 포인터 중 어떤 값을 키우는 게 맞을지 고민했다.

둘 중에 하나를 기준으로 가는게 가장 확실한 방법이라고 생각하여 앞의 쪽 포인터를 기준으로 두고 뒤쪽 포인터를 초기화시키는 방향으로 알고리즘을 구성했다.

 

근데 이 알고리즘의 단점은 j를 다시 초기화시키므로 O(N^2)으로 알고리즘이 구성되는 것이다.

function averagePair(arr, avg){
  let i = 0
  let j = arr.length - 1 
  if(arr.length<=1){
      return false
  }
  while(i<j){
      let sum = arr[i] + arr[j]
      if(sum === avg * 2){
          return true
      }

    if(sum>avg*2){
        j--
    } else{
        i++
    }
  }
  return false
}

배열이 정렬이 되어있다는 점을 착안하면 굳이 포인터를 초기화시키지 않아도 무방하다. 위의 알고리즘은 O(N)으로 동작하기에 더 낫다고 볼 수 있다.

 

문제2

 

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

 

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

 

왼쪽에 있는 문자열의 순서를 오른쪽에 있는 문자열이 가지고 있는지 확인하는 알고리즘을 묻는 문제이다.

고등학교 확통에서 a는 반드시 b의 오른쪽에 위치해야된다는 식의 문제랑 비슷하다.

 

처음 든 생각

1. 포인터를 두 개의 문자열을 각자 두어 하나씩 옮겨가며 확인을 한다.

2. 만약 str1의 포인터가 끝났을때 str2 포인터가 아직 남아있다면 순서대로 다 읽은 거니깐 맞는거 아니면 틀린거

3. 즉 기준이 str1의 포인터가 되어야 한다.

function isSubsequence(str1, str2) {
  // str1 포인터, str2 포인터 따로 설정
  let i = 0
  let j = 0
  
  while(i<str1.length){
  	  // str1 아직 다 안 읽었는데 str2 다 읽었으면 false
      if(j===str2.length){
          return false
      }
      // 같은 거 찾으면 둘다 오른쪽으로 한 칸씩 이동 아니면 str2만 오른쪽으로 이동
      if(str1[i] === str2[j]){
          i++
          j++
      } else{
          j++
      }
  }
  return true
}

처음에는 문제를 이렇게 풀었으나 겹치는 부분이 발견됐다. if조건문의 조건이 성립하든 안하든 어쨌든 j는 오른쪽으로 한 칸씩 이동해야 한다.

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

코드의 중복을 제거한 알고리즘은 위와 같다.