[백준, BOJ 9024] 두 수의 합 (java)

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

메모리: 231,292 KB , 시간: 2,072 ms

사용 알고리즘: 정렬, 이분 탐색, 두 포인터

728x90

---

처음엔 TreeSet으로 K - arr[i]에 해당하는 수가 있는지(contains) 검사하고,

없다면 큰 수 중 가장 작은 수(higher)와 작은 수 중 가장 큰 수(lower)를 검사해서 구했었다.

-> 메모리 초과

 

그다음 이분 탐색으로 K - arr[i]보다 작은 수 중 가장 큰 수를 구하고, 이분 탐색으로 구한 수와 그 수보다 큰 수 중 가장 작은 수를 비교하여 구했다.

정답은 뜨는데, 주석 쓰고 다시 돌렸더니 메모리 초과... 같은 코드 다시 돌렸는데 또 정답

약간 불안 불안한 듯.. 문제 풀고 투 포인터로 풀 수 있다는 거 알고 투 포인터로도 풀었다.

 

투 포인터는 코드짜기 제일 쉽고 깨끗한데 제일 안정적으로 정답 뜬다.

왜 투 포인터 생각을 못했지?

 

이분 탐색

메모리: 276,896 KB , 시간: 2,264 ms

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

public class Main {

    static int n, K;
    static int[] arr;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder answer = new StringBuilder();

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

        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            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 min = Integer.MAX_VALUE;
            int result =0;

            int[] ret;
            for (int i = 0; i < n - 1; i++) {
                // 이분탐색으로
                ret = getMinSub(i, i + 1, n - 1);

                if(min > ret[0]) {
                    min = ret[0];
                    result = ret[1];
                }
                else if(min == ret[0]) {
                    result += ret[1];
                }
            }

            answer.append(result + "\n");
        }

        System.out.print(answer);
    }

    // start부터 end까지 index와의 합이 K와 가장 가까운 수의 차 구하기
    private static int[] getMinSub(int index, int start, int end) {

        int[] ret = new int[2];
        ret[0] = Integer.MAX_VALUE;

        // 찾고자 하는 수
        int find = K - arr[index];

        int mid, get = start;
        while(start <= end) {
            mid = (start + end) / 2;

            if(arr[mid] > find) end = mid - 1;
            else {
                get = mid;
                start = mid + 1;
            }
        }

        // 찾은 수
        int sub = Math.abs(K - (arr[index] + arr[get]));
        if(ret[0] > sub) {
            ret[0] = sub;
            ret[1] = 1;
        }
        else if(ret[0] == sub) {
            ret[1]++;
        }

        // 찾은 수보다 더 큰 수 중 가장 작은 수도 검사
        if(get != n - 1) {
            sub = Math.abs(K - (arr[index] + arr[get + 1]));
            if(ret[0] > sub) {
                ret[0] = sub;
                ret[1] = 1;
            }
            else if(ret[0] == sub) {
                ret[1]++;
            }
        }

        return ret;
    }
}

투 포인터

메모리: 231,292 KB , 시간: 2,072 ms

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

public class Main {

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder answer = new StringBuilder();

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

        int n, K;
        int[] arr;
        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            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 min = Integer.MAX_VALUE;
            int result = 0;

            int start = 0, end = n - 1;
            int sub;
            while(start < end) {

                sub = Math.abs(K - (arr[start] + arr[end]));
                if(min > sub) { // 차가 더 작은 조합 찾음
                    min = sub;
                    result = 1;
                }
                else if (min == sub) { // 가장 작은 차 조합 하나 더 찾음
                    result++;
                }

                if(arr[start] + arr[end] < K) { // K보다 작으면 더 크게
                    start++;
                }
                // K보다 크면 더 작게
                else end--;
            }

            answer.append(result + "\n");
        }

        System.out.print(answer);
    }
}