Two Pointers

개념

• 문제를 풀기 위해 봐야 할 넓은 영역 중에서 볼 필요가 없는 부분들은 가능하면 안 볼 수 있게 하는 알고리듬
• 화살표 2개에 의미를 부여해서 탐색 범위를 압축하는 방법!

대표적인 카테고리

• 1차원 배열 위에 2개의 포인터를 만드는 경우
• 관찰을 통해 문제에 등장하는 변수 2개의 값을 포인터로 표현하려는 경우

포인터를 조작하는 방향에 대해서

• 2개의 포인터를 같은 방향으로 이동
• 2개의 포인터가 양끝에서 서로를 향해 이동

 

Two Pointers 문제들이 가지는 키워드

• 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"
• 곱의 최소

 

문제 풀이

BOJ 1806 - 부분합

• 난이도 : 3
• 10 <= N < 100,000
• 0 < S <= 10⁸
• 1 <= 각 원소 <= 10,000
• 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이

int 가능?

• 정답은 N 이하이므로 가능
• 모든 원소의 총합은 10⁹이므로 가능

시간복잡도 : O(N)

• L의 이동 횟수 N번
• R의 이동은 이전의 R부터 시작해서 이동
• L, R이 각자 최대 N번 이동

static void solve() {
	int R = 0, sum = 0, ans = n + 1;
    for (int L = 1; L <= n; L++) {
    	// L - 1 을 구간에서 제외
        sum -= a[L - 1];
        
        // R을 옮길 수 있을 만큼 옮기기
        while (R + 1 <= n && sum < S)
        	sum += a[++R];
            
        // [L ... R] 의 합, 즉 sum 이 조건을 만족할 때 정답 갱신
        if (sum >= S) ans = Math.min(ans, R - L + 1);
    }
    
    // ans 값 가능 여부 판단
    if (ans == n + 1) ans = 0;
    System.out.println(ans);
}

 

응용 문제 풀이

BOJ 13144 - List of Unique Numbers

• 난이도 : 4
• 1 <= N < 100,000
• 1 <= 각 원소 <= 100,000
• 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수

int 가능?

• N이 10만이며, 모든 숫자가 다르다면 모든 연속 구간이 모두 정답에 count
• N + (N - 1) + ... + 2 + 1 ≅ 50억
• int 불가능, long 타입 사용

Two Pointers 접근 방법

• 만약 1부터 3까지 중복된 것이 없었다면 2부터 3까지도 중복된 것이 없다는 뜻
• 1 ~ 100,000 까지 각 숫자별로 등장 횟수를 기록하는 count 배열을 따로 이용해서 체크
• L이 이동할 때마다 L의 위치에 있던 숫자에 대한 count는 다시 줄여줘야 함

static void solve() {
	long ans = 0;
    
    for (int L = 1, R = 0; L <= N; L++) {
    	// R 을 옮길 수 있을 만큼 옮기기
    	while (R + 1 <= N && cnt[A[R + 1]] == 0) {
        	R++;
            cnt[A[R]]++;
        }
        
        // 정답 갱신
        ans += R - L + 1;
        
        // L 을 옮기면서 A[L] 개수 감소
        cnt[A[L]]--;
    }
    
    System.out.println(ans);
}

 

BOJ 16472 - 고냥이

• 난이도 : 3
• 1 <= 알파벳 종류 N <= 26
• 1 <= 문자열 길이 <= 100,000
• 최대 N개의 종류를 가진 ⭐️연속된 문자열 밖에 인식하지 못하는 고냥이가 인식할 수 있는 최대 문자열 길이는?
• 이 문제를 봤을 때, 연속된 문자열이라는 키워드를 보고 Two Pointers 문제라는 것을 인지할 수 있어야 함!
• 정답의 최대치 = 문자열의 최대치인 10만

static void add(char c) {
	cnt[c - 'a']++;
    // 새롭게 나타난 알파벳이라면 읽은 종류 늘리기
    if (cnt[x - 'a'] == 1) kind++;
}

static void erase(char c) {
	cnt[c - 'a']--;
    // 인식해야 하는 알파벳에서 빠졌다면 읽은 종류 줄이기
    if (cnt[x - 'a'] == 0) kind--;
}

static void solve() {
	int len = A.length(), ans = 0;
    for (int R = 0, L = 0; R < len; R++) {
    	// R 번째 문자를 오른쪽에 추가
    	add(A.charAt(R));
        
        // 추가할 수 없다면 가능할 때까지 L을 이동
        while (kind > N) {
        	erase(A.charAt(L++));
        }
        
        // 정답 갱신
        ans = Math.max(ans, R - L + 1);
    }
    
    System.out.println(ans);
}