[백준 9024] 두 수의 합 Java 풀이

9024번: 두 수의 합

 

접근

n이 최대 1,000,000이므로 이중 for 문으로 문제를 풀 경우 시간 복잡도가 O(n^2)이 되어 시간 초과가 발생합니다. 따라서 투 포인터 기법을 이용하여 시간 복잡도를 O(n)으로 줄여 문제를 해결해야 합니다.

 

풀이

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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			int[] arr = new int[n];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			// 1. 배열 arr를 오름차순으로 정렬한다.
			Arrays.sort(arr);

			// 2. 투 포인터를 이용하여 k에 가장 가까운 두 정수의 조합의 수를 구한다.
			int left = 0, right = n - 1, count = 0;
			int minDiff = Integer.MAX_VALUE;
			while (left < right) {
				int sum = arr[left] + arr[right];
				int diff = Math.abs(k - sum);

				if (diff < minDiff) {
					minDiff = diff;
					count = 1;
				} else if (diff == minDiff) {
					count++;
				}

				if (sum > k) {
					right--;
				} else if (sum < k) {
					left++;
				} else {
					left++;
					right--;
				}
			}
			sb.append(count).append("\n");
		}

		// 결과 출력
		System.out.println(sb);
	}
}