[BaekJoon] 9024 두 수의 합

1.  문제 링크

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

2.  문제

요약

• 서로 다른 정수 집합 S에 속하는 서로 다른 두 개의 정수의 합이 K에 가장 가까운 두 정수 조합의 개수를 구하는 문제입니다.
• 입력
  • 첫 번째 줄에 테스트 케이스의 개수 t가 주어지고 두 번째 줄부터 한 개의 테스트 케이스에 해당하는 데이터가 주어집니다.
  • 각 테스트 케이스의 첫 번째 줄에는 2보다 크거나 같고 1,000,000보다 작거나 같은 집합 S에 있는 서로 다른 정수의 개수 n과 -10^8보다 크거나 같고 10^8보다 작거나 같은 K가 주어집니다.
  • 각 테스트 케이스의 두 번째 줄에는 -10^8보다 크거나 같고 10^8보다 작거나 같은 각각의 정수들이 n개 주어집니다.
• 출력: 각 테스트 케이스의 순서대로 각 테스트 케이스의 집합 S에 속하는 서로 다른 두 개의 정수의 합이 K에 가장 가까운 두 정수 조합의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	public int getNearestDif(int dif, int[] nums) {
		Arrays.sort(nums);
		int left = 0;
		int right = nums.length - 1;
		int near = Integer.MAX_VALUE;
		int count = 0;
		while(true) {
			int sum = nums[left] + nums[right];
			if(Math.abs(sum - dif) == near) {
				count++;
			} else if(Math.abs(sum - dif) < near) {
				count = 1;
				near = Math.abs(sum - dif);
			}
			if(sum == dif) {
				left++;
				right--;
			} else if(sum < dif) {
				left++;
			} else {
				right--;
			}
			if(left >= right) {
				break;
			}
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int test_num = Integer.parseInt(br.readLine());
		Main m = new Main();
		for(int i = 0; i < test_num; i++) {
			String[] input = br.readLine().split(" ");
			int num = Integer.parseInt(input[0]);
			int dif = Integer.parseInt(input[1]);
			int[] nums = new int[num];
			input = br.readLine().split(" ");
			for(int j = 0; j < num; j++) {
				nums[j] = Integer.parseInt(input[j]);
			}
			bw.write(m.getNearestDif(dif, nums) + "\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 투 포인터를 이용하여 해결할 수 있는 문제입니다.
• 집합 S에 있는 정수들을 오름차순으로 정렬한 뒤, 왼쪽 포인터를 가장 작은 수에, 오른쪽 포인터를 가장 큰 수에 놓고 시작합니다.
• 왼쪽 포인터가 오른쪽 포인터보다 작을 때까지 두 포인터에 해당하는 정수들을 확인하여 두 정수의 합을 구하고 두 정수의 합과 주어진 K와의 거리를 구하여 가장 가까운 두 정수의 합을 구합니다.
• 만약 현재 두 포인터가 있는 위치에서의 두 정수의 합이 이전 두 정수의 합들에서 K에 가장 가까운 합과 같다면 두 정수 조합의 개수를 1 증가시킵니다.
• 만약 현재 두 포인터가 있는 위치에서의 두 정수의 합이 이전 두 정수의 합들보다 K에 더 가깝다면 두 정수 조합의 개수를 1로 초기화하고 K에 가장 가까운 두 정수의 합을 현재 구한 두 정수의 합으로 변경합니다.
• 포인터를 이동시킬 때는

  • 만약 현재 두 포인터가 있는 위치에서의 두 정수의 합이 주어진 K보다 작다면 왼쪽 포인터를 오른쪽으로 한 칸 이동시킵니다.

  • 만약 현재 두 포인터가 있는 위치에서의 두 정수의 합이 주어진 K보다 크다면 오른쪽 포인터를 왼쪽으로 한 칸 이동시킵니다.

    • 만약 현재 두 포인터가 있는 위치에서의 두 정수의 합이 주어진 K와 같다면 왼쪽 포인터는 오른쪽으로 한 칸, 오른쪽 포인터는 왼쪽으로 한 칸 이동시킵니다.

1. 주어진 집합 S의 정수들을 오름차순으로 정렬합니다.
2. 왼쪽 포인터를 집합 S의 처음 위치에, 오른쪽 포인터를 집합 S의 끝 위치에 위치시킵니다.
3. K에 가장 가까운 두 정수의 합을 저장할 변수 near를 생성하고 정수의 최댓값으로 초기화시키며 두 정수 조합의 개수를 나타낼 count 변수를 생성하고 0으로 초기화합니다.
4. 무한루프를 돌며 서로 다른 두 정수의 합이 K에 가장 가까운 두 정수 조합의 개수를 구하고 왼쪽 포인터가 오른쪽 포인터보다 크거나 같다면 해당 루프를 빠져나옵니다.
   1. 왼쪽 포인터와 오른쪽 포인터에 해당하는 두 정수의 합을 구합니다.
   2. 만약 두 정수의 합이 이전에 구했던 K에 가장 가까운 두 정수의 합과 같다면 두 정수 조합의 개수를 나타내는 count 변수를 1 증가시킵니다.
   3. 만약 두 정수의 합이 이전에 구했던 K에 가장 가까운 두 정수의 합보다 K에 가깝다면 count 변수를 1로 초기화시키고 K에 가장 가까운 두 정수의 합을 나타내는 near의 값을 현재 두 정수의 합으로 변경합니다.
   4. 만약 현재 두 정수의 합이 주어진 K와 같다면 왼쪽 포인터를 오른쪽으로 한 칸, 오른쪽 포인터를 왼쪽으로 한 칸 이동시킵니다.
   5. 만약 현재 두 정수의 합이 주어진 K보다 작다면 왼쪽 포인터를 오른쪽으로 한 칸 이동시킵니다.
   6. 만약 현재 두 정수의 합이 주어진 K보다 크다면 오른쪽 포인터를 왼쪽으로 한 칸 이동시킵니다.