백준 3273번 <두 수의 합> with 이진탐색

백준 알고리즘 3273번

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

3273번: 두 수의 합

---

3273번

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

 

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

 

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

---

문제 해결

이진 탐색으로 문제를 해결했다.

수열이 n개의 서로 다른 양의 정수로 이루어졌기 때문에 ai + aj = x를 만족하는 쌍은 ai에 대해 하나의 aj 값을 갖는다.

 

각 수열의 값을 기준으로 이진 탐색을 하는데 이때 찾는 데이터는 x - ai의 값이다.

중복으로 찾는 경우를 방지하기 위해 visit 배열을 통해 이미 찾은 쌍의 숫자는 표시를 해두었다.

(이진 탐색은 정렬되어 있는 것을 기준으로 하기 때문에 수열을 정렬해야 한다.)

---

코드

package bj3273;

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

public class Main {
	static int[] number;
	static boolean[] visit;

	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());
		number = new int[n];
		visit = new boolean[n];
		if (n == 1) {
			System.out.println(0);
			System.exit(0);
		}
		for (int i = 0; i < n; i++) {
			number[i] = Integer.parseInt(inArr[i]);
			visit[i] = false;
		}
		Arrays.sort(number);
		int answer = 0;
		for (int i = 0; i < n; i++) {
			if (visit[i]) {
				continue;
			}
			int data = x - number[i];
			int idx = BS(n, data);
			if (idx == -1 || idx == i) {
				continue;
			}
			visit[i] = true;
			visit[idx] = true;
			answer++;
		}
		System.out.println(answer);

	}

	public static int BS(int n, int data) {
		int start = 0;
		int end = n - 1;
		while (start <= end) {
			int mid = (start + end) / 2;
			if (number[mid] > data) {
				end = mid - 1;
			} else if (number[mid] == data) {
				return mid;
			} else {
				start = mid + 1;
			}
		}
		return -1;
	}

}

---

결과

---