백준 9024번 - 두 수의 합(Java, 자바)

문제 링크

문제 설명

여러 개의 서로 다른 정수 S = {a₁, a₂, …, a_n} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수

S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}

가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -10⁸ ≤ K ≤ 10⁸ )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 10⁸ 이고, 최솟값은 -10⁸ 이다. 잘못된 데이터가 입력되는 경우는 없다.

출력

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스의 출력되는 첫 줄에 입력으로 주어진 n 개의 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수 K 에 가장 가까운 두 정수의 조합의 수를 출력한다.

문제 풀이 방법

투포인터를 이용해서 가볍게 풀 수 있는 문제이다.
단 여기서 타켓 숫자와 같지 않아도 가까운 조합도 가능하므로 이것을 고려하는 방법에 대해 생각을 해야한다.

우선 위와 같은 입력값이 주어졌다고 가정하자.
배열이 먼저 주어졌으면 투포인터를 쓰기 위해서 정렬을 먼저 한다.

투포인터는 배열 시작과 끝 부분에 위치한다.

투포인터의 값들을 더한다.
이때 더한 값이 curGap 이 된다. 최소 차이를 저장하는 Gap 변수와 비교하여 Gap 이 더 클 때 answer = 0 으로 초기화 시킨 다음 Gap 을 curGap 으로 업데이트를 한다.

그런 다음 right 부분을 앞으로 한칸 땡겨서 다시 또 값을 비교한다.
이것을 left < right 범위안에서 계속 반복하면 된다.

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());

        for (int i = 0; i < test; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            System.out.println(find(k, arr));
        }
    }

    public static int find(int target, int[] arr){
        int answer = 0;
        int left = 0;
        int right = arr.length - 1;

        Arrays.sort(arr);
        int gap = Integer.MAX_VALUE;

        while (left < right){
            int sum = arr[left] + arr[right];
            int curGap = Math.abs(sum - target);
            if(gap >= curGap){
                if(gap > curGap){
                    answer = 0;
                }
                answer++;
                gap = curGap;
            }

            if(sum >= target){
                right--;
            }
            else{
                left++;
            }
        }

        return answer;
    }
}