[Algorithm] 99클럽 코테 스터디 5일차 TIL | 백준_두 용액(2470번)

 

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

---

이전과 비슷한 이분탐색 문제라고 생각하고 처음 문제를 봤을 때 low랑 high 초기화를 어떤 수로 해야 되지?

mid는 뭐랑 비교해??? 하며 혼란이 있었다.

 

서치해보니 이 문제는 투 포인터를 사용하는 문제라고 한다.-_-

 

투 포인터란? 정렬된 배열에서 두 개의 포인터를 사용해서 특정 조건을 만족하는 값을 찾는 알고리즘 기법이다.

즉. 배열의 첫번째 값을 left, 배열의 마지막 값을 right로 두고

두 합이 찾으려는 값보다 작으면 left를 오른쪽으로 이동 시키고 (합을 키우기 위해)

두 합이 찾으려는 값보다 크면 right를 왼쪽을 이동 시킨다. (합을 줄이기 위해)

 

일단 이 개념을 숙지해두고 풀어나가기 시작했다!

 

이 문제에서는 mid 대신 min 즉 최솟값을 사용하여 값을 찾아가야한다.

두 수의 합을 min값과 비교해가며 갱신한다.

 

0과 가까운 수가 되어야 하기 때문에 두 수의 합은 절대값 함수를 사용해서 비교했다. (Math.abs(int a, int b))

 

나의 풀이🔽

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        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[] answer = new int[2];

        int left = 0;
        int right = N-1;
        int min = Math.abs(arr[left] + arr[right]);
        answer[0] = arr[left];
        answer[1] = arr[right];

        while(left < right){
            int sum = arr[left] + arr[right];
            if(Math.abs(sum) < min){
                min = Math.abs(sum);
                answer[0] = arr[left];
                answer[1] = arr[right];
                if(min == 0) break;
            }
            if(sum < 0){
                left++;
            }else{
                right--;
            }
        }

        System.out.println(answer[0] + " " + answer[1]);
    }
}

 

 

while(left < right){
    if(arr[left] + arr[right] < 0){
        left++;
    }else{
        right--;
    }
    if(Math.abs(arr[left] + arr[right]) < min){
        min = Math.abs(arr[left] + arr[right]);
        answer[0] = arr[left];
        answer[1] = arr[right];
        if(min == 0) break;
    }
}

첨에 이렇게 풀었다가 맞왜틀?? 이러고 있었네ㅜ

left, right 포인터 이동 후 최솟값을 갱신하고 있어서 정답이 아님

(이동 전 값이 최솟값이 될 수 있는데 이 경우의 수를 무시해버리는 격)

항상 포인터 이동 전에 현재 계산값이 최소값을 갱신할 수 있는지 확인해야한다