Algorithm - Two Pointers Algorithm

Two Pointers Algorithm

• 2개의 배열 혹은 리스트를 하나의 배열이나 리스트로 정렬할 때 사용한다.

• 2중 for 문을 사용하지 않고, 배열끼리를 서로 비교하며 정렬하는 것이므로, for 문을 한 번만 사용할 수 있다.

• 아래는 Two Pointers Algorithm 을 활용하여 2개의 배열을 1개의 배열로 만들어 오름차순 정렬하는 것이다.

   public static List<Integer> solution(int aCount, int bCount, int[] aArr, int[] bArr) {
       List<Integer> answer = new ArrayList<>();
       Arrays.sort(aArr);
       Arrays.sort(bArr);
       int p1, p2;
       p1 = p2 = 0;
       while ( p1 < aCount && p2 < bCount ) {
           if ( aArr[p1] < bArr[p2] ) {
               p1++;
           } else if ( bArr[p2] < aArr[p1] ) {
               p2++;
           } else {
               answer.add(aArr[p1++]);
               p2++;
           }
       }
       return answer;
   }
  

• 그 외에도 pS 와 pE 를 활용한 Two Pointers Algorithm 도 있다.

• 예를 들면, 0 과 1이 있는 배열 속에서 0을 최대 2개까지만 1로 치환 하였을 경우, 가장 많이 1이 연속 되는 횟수를 구하는 문제가 있다.

• 다음은 그러한 문제인, 최대 길이 연속 부분 수열을 구하는 코드이다.

   public static int solution(int n, int k, int[] arr) {
       int answer = 0;
       int cnt = 0; // k에 대한 카운트
       int pS = 0;
       for ( int pE=0; pE<n; pE++ ) {
           if ( arr[pE] == 0 ) cnt++;
           while(cnt>k) {
               if ( arr[pS] == 0 ) cnt--;
               pS++;
           }
           answer = Math.max(answer, pE-pS+1);
       }
       return answer;
   }
  

• 연속해서 뭔가를 구해야하거나, 2개의 배열을 가지고 정렬이나 특정 합일경우를 카운트 하는 문제는 Two Pointers Algorithm 을 사용해라.

• 2개의 배열로 정렬해서 하나의 배열을 만들거나, 2개의 배열에 공통된 숫자만 정렬해서 하나의 배열에 담는 문제는 two pointers 알고리즘을 사용해라.

• 갯수가 일정하지 않고, 합이 얼마인지 고정이라면 ( ex. 연속된 수의 합이 5일 경우) two pointers 알고리즘을 사용해라.

• two pointers 알고리즘에는 2종류가 있다.

  • 하나는 2개의 배열을 가지고 a배열 b배열을 비교해가며 a 인덱스, b 인덱스를 증가시켜가는 것

  • 다른 하나는 하나의 배열속에서 pS, pE를 지정하여 특정경우에는 pS를 특정 경우에는 pE를 증가시켜가는 방법이 있다.