백준 5972번: 택배 배송[JAVA]

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

2467번: 용액

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = 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());
        }

        int left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE; // 현재 알고있는 최솟값
        int[] answer = new int[2];
        while (left < right) {
            int sum = Math.abs(arr[left] + arr[right]); // 새로운 최솟값
            if (sum < min) { // 새로운 최솟값이 원래 알고있는 최솟값보다 더 작다면 갱신
                min = sum;
                answer[0] = arr[left];
                answer[1] = arr[right];
            }
            if (sum == 0) {
                break;
            }
            if (arr[left] + arr[right] > 0) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

 

[설명]

간단한 이분탐색 알고리즘 문제이다. 다른 이분탐색 알고리즘과 다른점은 left 와 right 가 arr배열의 인덱스 내에서만 이루어져야만 한다는것을 조심해야한다.

left는 0 (첫번째 인덱스), right는 N - 1 (마지막 인덱스)로 초기화하고 left가 right를 넘어갈때 까지 반복한다.

left 와 right를 더한 값이 0 이상일 경우 right-- 아닐 경우 left ++ 한다.

혹은 0 일경우 바로 출력한다.