백준 자바 3273번 두 수의 합 - 투 포인터 개념

오늘은 백준 3273번 풀이를 통해 투 포인터의 개념에 대해 알아보겠습니다.

최초의 시도로 그림으로 넣어봤는데 이해를 도왔으면 좋겠습니다.

 

먼저, 투포인터는 start포인터와 end포인터 두개의 포인터가 존재한다는 것입니다.

정렬을 통해 배열을 만들어두고 가장 작은곳에 start 가장 큰곳에 end를 찍겠습니다.

 

 

 

작을때의 케이스를 넣지못해서 아쉬움이있으나 이제 구현하러 가봅시다.

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


public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		
		StringTokenizer st;
		st =  new StringTokenizer(br.readLine()," "); 
		
		for (int i=0; i< arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);	
		
		int x = Integer.parseInt(br.readLine());
		
		int count = 0;
		int start_idx = 0;
		int end_idx = N-1; // <- 0번 인덱스부터 시작하기 때문에 
        // 마지막 인덱스를 가르키기 위해 -1을 해줍시다.
		
		while (start_idx < end_idx) //시작 인덱스와 끝 인덱스가 동일하면 중단!{
			if (arr[start_idx] + arr[end_idx] < x) {
				start_idx++;
			}
			
			else if (arr[start_idx] + arr[end_idx] > x) {
				end_idx--;
			}
			
			else if (arr[start_idx] + arr[end_idx] == x) {
				count++;
				start_idx++;
				end_idx--;
				
			}
		

		}
		System.out.println(count);
	}
}