백준 3273번 <두 수의 합> with 2 pointer

백준 알고리즘 3273번

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

---

3273번

n개의 서로 다른 양의 정수로 이루어진 수열 a와 자연수 x가 주어졌을 때, ai + aj = x를 만족하는 (ai, aj) 쌍의 수를 구하여라.

 

입력으로 첫 줄에 수열의 크기 n이 주어지고 그 다음 줄에 수열에 포함되는 n개의 수가 주어진다. 셋째 줄에는 x가 주어진다.

 

출력으로 ai + aj = x를 만족하는 쌍의 개수를 구해서 출력하면 된다.

---

문제 해결

two pointer를 이용하여 문제를 해결하였다. 먼저 number 배열을 정렬한다.

pointer 하나(start)는 0부터 시작하고, 다른 하나(end)는 n-1 부터 시작한다. start는 1씩 더해가고 end는 1씩 빼간다.

number[start] + number[end]의 값이 x와 같다면 count를 한 후 start에는 1을 더하고 end에는 1을 뺀다.

x 보다 크다면 end에 1을 빼고 (x보다 크기 때문에 end의 값을 줄여서 더 작은 값으로 만들어야 한다.)

x 보다 작다면 start에 1을 더한다. (x보다 작기 때문에 start의 값을 키워서 더 큰 값으로 만들어야 한다.)

 

end와 start가 범위를 벗어나면 while문을 종료하고 start의 값이 end의 값보다 크거나 같아도 while문을 종료한다.

---

코드

package bj3273;

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

public class Main2 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] inArr = br.readLine().split(" ");
		int x = Integer.parseInt(br.readLine());
		int[] number = new int[n];
		if (n == 1) {
			System.out.println(0);
			System.exit(0);
		}
		for (int i = 0; i < n; i++) {
			number[i] = Integer.parseInt(inArr[i]);
		}
		Arrays.sort(number);
		int answer = 0;
		int start = 0;
		int end = n-1;
		while(start < end) {
			if(start == n || end == -1) {
				break;
			}
			int temp = number[start] + number[end];
			if(temp == x) {
				answer++;
				start++;
				end--;
			}else if(temp > x) {
				end--;
			}else {
				start++;
			}
		}
		System.out.println(answer);
		
	}

}

---

결과

---

투포인터로 푼 것이 이진 탐색으로 푼 것보다 빠르다.