[자바] 백준 9024 - 두 수의 합 (java)

 문제 : boj9024

---

 

필요 알고리즘 개념

• 정렬, 투 포인터
  
  • 투 포인터로 해결 가능한 문제이다. 투 포인터 사용을 위해 정렬도 해줘야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  두 정수의 합이 K와 가장 가까운 두 정수의 조합의 수를 찾는 문제이다. 얼핏 K와 동일한 수가 아니라 K와 가장 가까운 두 정수를 찾는거여서 투 포인터로 해결이 안된다고 생각할 수 있다. (예를들어 K=8이고, 두 정수의 합이 8인 경우가 없고, 7이나 9인 경우는 있다면 7과 9인 모든 조합의 수를 찾아야 한다.)

 

  '서로 다른 정수' 라는 조건이 없었다면 투 포인터 기본 형태로 당연히 풀 수 없었는데, 해당 조건이 써있으므로 기본적인 형태의 투 포인터로 풀면 된다. 로직은 이하와 같다.

 

1. 각 테스트케이스마다

 

2. N개의 정수를 입력받은 후 정렬한다.

 

3. 가장 작은 수는 s라는 포인터가, 가장 큰 수는 e라는 포인터가 가리키게 할 것이다. 그럼 s+e >= K 라면 e--, s+e<K 라면 s++ 를 해주면 된다. 여기서 '서로 다른 정수'라는 조건이 없었다면 s와 e의 위치를 기억해뒀다가 e를 고정한 후 s++와 s를 고정한 후 e--를 전부 확인하거나, 애초에 동일한 수는 별도로 카운팅해둬서 풀어야 한다. 이걸 왜 말하냐면 '서로 다른 정수' 부분을 못보고 저렇게 풀다가 저거 보고 다시 짰기 때문이다 ㅜ

 

4. 아무튼 '3'의 로직은 고정이고 그럼 매번 K와 s+e의 차이를 확인해서 정답을 구해주면 된다.

 

---

 

코드 : github

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer 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());
            }
            Arrays.sort(arr);

            int s = 0, e = n-1;
            int minGap = Integer.MAX_VALUE;
            int answer = 0;
            while (s<e) {
                int sum = arr[s] + arr[e];
                int gap = Math.abs(sum-k);
                if (minGap >= gap) {
                    if (minGap > gap) answer = 0;
                    minGap = gap;
                    answer++;
                }

                if (sum >= k)
                    e--;
                else
                    s++;
            }
            sb.append(answer).append('\n');
        }
        System.out.print(sb);
    }
}