[알고리즘] 투 포인터

안수진·2023년 5월 31일

이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간 제한은 2초이다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터이다.
연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하겠다. 시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 문제에 접근해 보겠다.

- 슈도코드 작성하기

N 변수 저장
사용 변수 초기화 (count = 1, start_index = 1, end_index = 1, sum = 1)
while(end_index != N){
	if(sum == N) count증가, end_index증가, sum값 변경
    else if(sum > N) sum값 변경, start_index증가
    else if(sum < N) end_index증가, sum값 변경
}
count 출력하기

- 제출 코드

import java.util.Scanner;

public class Baekjoon2018 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int count = 1;
		int start_index = 1;
		int end_index = 1;
		int sum = 1;
		
		while(end_index != N) {
			if(sum == N) {
				count++;
				end_index++;
				sum += end_index;
			}
			else if(sum > N) {
				sum -= start_index;
				start_index++; 
			}
			else { //sum < N
				end_index++;
				sum += end_index;
			}
		}
		System.out.println(count);
	}
}

🔎백준 1940번: 주몽

- 문제 분석하기

우선 시간 복잡도를 고려해보자. 두 재료의 번호의 합, 즉, 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있습니다. N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없다.
일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)이다. 즉, 정렬을 사용도 괜찮다. 입력받은 N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근해 보겠다.

투 포인터 이동 원칙

A[i] + A[j] > M: j--; //번호의 합이 M보다 크므로 큰 번호 index를 내린다.
A[i] + A[j] < M: i++; //번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
A[i] + A[j] == M: i++; j--; count++; //양쪽 포인터를 모두 이동시키고 count를 증가시킨다.

- 슈도코드 작성하기

N(재료의 개수), M(갑옷이 되는 번호) 저장하기
for(N만큼 반복){
	재료 배열 저장하기
}
재료 배열 정렬하기
while(i < j)
{
	if(재료 합 < M) 작은 번호 재료를 한 칸 위로 변경하기
    else if(재료 합 > M) 큰 번호 재료를 한 칸 아래로 변경하기
    else 경우의 수 증가, 양쪽 index 각각 변경하기
}
count 출력하기

- 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Baekjoon1940_주몽 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		int [] A = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(A);
		int count = 0;
		int i = 0; //A[0] -> Min
		int j = N-1; //A[N-1] -> Max
		
		while(i < j){
			if(A[i] + A[j] < M) i++;
			else if(A[i] + A[j] > M) j--;
			else {
				count++;
				i++;
				j--;
			}
		}
		System.out.println(count);
		
	}
}

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
투 포인터 알고리즘과 매우 비슷하고 원리도 간단하다.

🔎백준 12891번: DNA 비밀번호

- 문제 분석하기

슬라이딩 윈도우 원리 이외에도 '실제 문자열과 관련된 배열 처리를 어떻게 할것인가?',
'비밀번호 유효성 검사를 보다 빠르게 할 수 있는 방법이 있을까? 등 코드 레벨에서 고민이 필요한 부분이 있다.

- 슈도코드 작성하기

//데이터 저장
S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkArr(비밀번호 체크 배열)

//변수 선언
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P 범위(0 ~ P-1)만큼 S 배열에 적용하고, 유효한 비밀번호인지 판단 필요
for(i를 P에서 S까지 반복){
	j 선언 (i - P)
}

- 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	static int myArr[];
	static int checkArr[];
	static int checkSecret;
	
    public static void main(String args[]) throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int S = Integer.parseInt(st.nextToken()); //문자열 크기
		int P = Integer.parseInt(st.nextToken()); //부분 문자열의 크기
		int Result = 0;
		checkArr = new int[4]; //몇 개의 문자와 관련된 갯수를 충족했는지 판단하는 변수
		myArr = new int[4]; //현재 상태 배열
		char A[] = new char[S]; //문자열 데이터
		checkSecret = 0; //몇 개의 문자가 충족했는지 카운트 -> 4가 되면 비밀번호 가능

		A = bf.readLine().toCharArray();
		st = new StringTokenizer(bf.readLine());
		for(int i = 0; i < 4; i++){
			checkArr[i] = Integer.parseInt(st.nextToken());
			if(checkArr[i] == 0){
				checkSecret++;
			}
		}

		for(int i = 0; i < P; i++){ //부분문자열 처음 받을때 세팅
			Add(A[i]);
		}

		if(checkSecret == 4) Result++;

		//슬라이딩 윈도우
		for(int i=P; i<S; i++){
			int j = i-P;
			Add(A[i]);
			Remove(A[j]);
			if(checkSecret == 4) Result++;
		}

		System.out.println(Result);
		bf.close();
		
	}

	
		static void Add(char c){
			switch(c){
			case 'A':
				myArr[0]++;
				if(myArr[0] == checkArr[0]) checkSecret++;
				break;
			case 'C':
				myArr[1]++;
				if(myArr[1] == checkArr[1]) checkSecret++;
				break;
			case 'G':
				myArr[2]++;
				if(myArr[2] == checkArr[2]) checkSecret++;
				break;
			case 'T':
				myArr[3]++;
				if(myArr[3] == checkArr[3]) checkSecret++;
				break;
			}
		}

	static void Remove(char c){
			switch(c){
			case 'A':
				if(myArr[0] == checkArr[0]) checkSecret--;
				myArr[0]--;
				break;
			case 'C':
				if(myArr[1] == checkArr[1]) checkSecret--;
				myArr[1]--;
				break;
			case 'G':
				if(myArr[2] == checkArr[2]) checkSecret--;
				myArr[2]--;
				break;
			case 'T':
				if(myArr[3] == checkArr[3]) checkSecret--;
				myArr[3]--;
				break;
			}
		}
        
}