백준 두 수의 합(9024)

 

이분 탐색 문제이다.

 

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

9024번: 두 수의 합

 

 

두 수의 합 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

2217

936

688

43.544%

문제

여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 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, -108 ≤ K ≤ 108 )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 108 이고, 최솟값은 -108 이다. 잘못된 데이터가 입력되는 경우는 없다.

출력

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

예제 입력 1 복사

4
10 8
-7 9 2 -4 12 1 5 -3 -2 0
10 4
-7 9 2 -4 12 1 5 -3 -2 0
4 20
1 7 3 5
5 10
3 9 7 1 5

 

투포인터로 가능한 문제이지만 이분탐색으로 풀어보았다 

 

정렬된 배열을 기준으로 K와 가장 작은 폭의 수를 카운팅하는 방식으로 이분 탐색을 진행하면 된다.

 

약간 조건을 만드는데 까다로움이 있지만 천천히 짜다보면 만들 수 있다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/9024
 */
public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        for (int k=0; k < t; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int[] nums = new int[N];

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

            Arrays.sort(nums);
            System.out.println(cal(nums, K));

        }
    }

    public static int cal(int[] nums, int K) {


            int count = 0;
            int min = Integer.MAX_VALUE;

            for (int i=0; i < nums.length; i++) {
                int left = i + 1;
                int right = nums.length - 1;

                while (left <= right) {

                    int mid = (left + right) / 2;

                    if (Math.abs(K - (nums[i] + nums[mid])) < min) {
                        count = 1;
                        min = Math.abs(K - (nums[i] + nums[mid]));
                    } else if (Math.abs(K - (nums[i] + nums[mid])) == min) {
                        count++;
                    }

                   if (K > (nums[i] + nums[mid])) {
                        left = mid + 1;
                    } else if (K < (nums[i] + nums[mid]))  {
                        right = mid - 1;
                    } else {
                       break;
                   }
                }
            }


        return count;
    }


}

 

결과