[JAVA][백준 2470] 두 용액

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

 

---

풀이 과정

주어진 용액을 두개를 더해 0과 가까운 용액을 만드는 것이 목표.

 

이 문제의 알고리즘 분류에 이분탐색이 있는데

사실 이분탐색을 사용하지 않고 투 포인터만 사용하면 쉽게 풀린다.

 

투 포인터로 푸는 방법은

일단 입력값을 배열에 받아 정렬을 하고

투 포인터를 이용해서 양 끝에서부터 용액을 선택한다음

0보다 크면 right값을 줄이고,
0보다 작으면 left값을 줄이면 된다.
시간 초과도 되지 않는다.

예전에 투 포인터로 풀었던 문제이지만 이분탐색도 곁들여서 풀면 좀 더 효율적으로 풀 수 있고
지금 계속 이분탐색을 연습중이라서 이분탐색을 넣은 방법으로 다시 해볼려고 한다.
이분탐색으로 푸는게 훨씬 어려운 방법인 것 같다...

현재로써는 그냥 배열을 0부터 N까지 돌면서 한개의 용액은 정해놓고 나머지 하나를 이분탐색으로 찾는 방법인데..
이게 투포인터로 푸는 것보다 효율적일까..?
투 포인터는 해봤자 O(N)인데...이분탐색으로 푼다면 O(NlogN)인 것 같은데...

이분탐색하기 연습이 아니라면 굳이긴하다.

풀이 과정은 

 

투포인터로 풀때

1. 배열을 정렬한 후

2. left = 배열의 0번째 인덱스, right = 배열의 N-1번째 인덱스를 두고

3. arr[left] + arr[right]가 양수면 right--, 음수이면 left++를 해주는 반복문을 돈다.
4. arr[left] + arr[right] == 0이라면 바로 반복문을 탈출하면 된다.

 

 

이분탐색으로 풀면

1. 똑같이 정렬하고

2. 기준점을 맨 왼쪽(맨 왼쪽이나 맨 오른쪽이나 상관없다.)으로 두고

3. 나머지 배열에서 짝으로 될 만한 숫자를 이분탐색하여 찾는다.

ex) 0번을 기준으로 한다면 1부터 N-1의 범위에서 이분 탐색. 그 다음엔 1을 기준으로 하고 2부터  N-1의 범위에서 이분 탐색

 

골드5 치고 별로 어렵지 않은 문제였다.

---

풀이 코드(투포인터)

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;

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

        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 left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE; // 0과의 차이

        int ans1 = 0;
        int ans2 = 0;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (Math.abs(sum) < min) {
                min = Math.abs(sum);
                ans1 = arr[left];
                ans2 = arr[right];
            }

            if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(ans1 + " " + ans2);
    }

}

 

풀이코드(이분탐색)

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

// 0과 가장 가까운 용액을 만드는 두 용액의 특성 값

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

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

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

        int ansAbs = Math.abs(arr[0] + arr[1]);
        int ans1 = arr[0];
        int ans2 = arr[1];
        for (int i = 0; i < N - 1; i++) {
            int pair = findPair(arr, i + 1, N - 1, arr[i]);
            int sumAbs = Math.abs(arr[i] + pair);
            if (ansAbs > sumAbs) {
                ansAbs = sumAbs;
                ans1 = arr[i];
                ans2 = pair;
            }
        }

        System.out.println(ans1 + " " + ans2);

    }

    private static int findPair(int[] arr, int start, int end, int value) {
        int pair = arr[start];
        int min = Math.abs(arr[start] + value);
        int left = start, right = end;

        while (left <= right) {
            int mid = (left + right) / 2;
            int sum = arr[mid] + value;
            int sumAbs = Math.abs(sum);
            if (sumAbs < min) {
                pair = arr[mid];
                min = sumAbs;
            }
            if (sum < 0) left = mid + 1;
            else if (sum > 0) right = mid - 1;
            else return arr[mid];
        }

        return pair;
    }
}

---

최근 간단한 문제만 풀다보니 자바에 이미 BinarySeach 메소드가 구현되어있는데

그냥 구현 연습하지 말고 다른걸 공부할까~~하다가

이 문제를 만나버렸다.

이 문제처럼 절댓값을 넣는다던지 변형이 필요한 상황이 종종 있기때문에

자료구조를 구현할 줄 아는 능력이 필요하다는 것을 다시금 느끼게 되었다..(나 자신 반성해)

 

 

뭔가 공부할건 많고 시간은 없고 그러다보니 요령을 피울려고 하는데

요령 피워봤자 남는거 별로 없다는 건 안다...

그렇지만 사람 마음이 맘대로 되는건 아니니깐ㅜ.ㅜ

 

가끔 블로그를 다시 돌아보면서 마음 다잡고 공부할 수 있는 원동력이 되었으면 좋겠다.