백준 9024 (두 수의 합) - 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} 등의 다섯 종류가 있다.

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

 

유형 : 투 포인터

 

접근 방식

• 투 포인터를 통해 K에 가장 가까운 값을 찾도록 탐색한다.

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int t;
    static int n,m;

    static int[] board = new int[1_000_001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();
        t = Integer.parseInt(st.nextToken());

        for(int a = 1 ; a <= t ; a++){
            st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine()," ");

            board = new int[n];
            for(int i = 0 ; i < n ; i++){
                board[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(board,0,n);
            int tmpCount = find();
            sb.append(tmpCount+"\n");
        }

        System.out.print(sb);
        br.close();
    }

    static int find() {
        int count = 0;
        int result = board[0] + board[n-1];

        int l = 0;
        int r = n - 1;
        int sum;

        while(l < r) {
            sum = board[l] + board[r];

            int abs1 = Math.abs(result - m);
            int abs2 = Math.abs(sum - m);

            if(abs1 == abs2) {
                count++;
            }else if(abs1 > abs2) {
                count = 1;
                result = sum;
            }

            if(sum < m) {
                l = l + 1;
            }else if(sum >= m) {
                r = r - 1;
            }
        }


        return count;
    }
}