[백준 - 9024][GOLD 5][해설 X] - 두 수의 합 (JAVA)

문제 링크

---

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

 

문제

---

여러 개의 서로 다른 정수 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 에 가장 가까운 두 정수의 조합의 수를 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int testcase =1 ; testcase<=t;testcase++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            int[]num = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            Arrays.sort(num);

            int l = 0;
            int r = num.length-1;

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

            //두 수의 조합을 만들기
            while(l<r){
                int sum = num[l] + num[r];
                int differ = Math.abs(k - sum);
                
                //더 작은 최소 차이를 찾은 경우
                if(minDiffer > differ){
                    count = 1;
                    minDiffer = differ;
                }
                //기존 최소 차이의 경우가 추가로 발견된 경우
                else if(minDiffer == differ){
                    count++;
                }

                //만약 목표 숫자 k 보다 두수의 합이 작으면 이미 r은 최대치이므로 l이 크게하여 두수의 합을 키운다.
                if(sum < k){
                    l++;
                }
                //만약 목표 숫자 k 보다 두수의 합이 크거나 같으면 이미 l은 최소치이므로 l이 작게하여 두수의 합을 작게 만든다.
                else{
                    r--;
                }
            }

            System.out.println(count);
        }
    }
}

 

 

실행 결과

---

 

 

팁

---

• 두 수의 합은 두 포인터로 해결할 수 있다.