[백준 No.3649] - 로봇 프로젝트(이분탐색)

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

예제 입력 1

1
4
9999998
1
2
9999999

예제 출력 1

yes 1 9999999

문제 Tip

아마 문제는 쉬운데 런타임 에러가 나거나, 시간초과가 나서 필요한 정보를 수집하러 오신분들을 위해 기재합니다.

[런타임 에러 시]
 문제를 잘 읽어보면 "입력은 여러 개의 테스트 케이스로 이루어져 있다."
 라고 적혀있다.
 예제가 1개 적혀있다고 해서 입력은 한번만 이뤄지는것이 아니다. 
 아랫 코드 12번 라인을 참고하면 될 것 같다.

[시간 초과 시]
  Set으로 풀려고 하신분이 계신다고해서... 알고리즘 분류가 이분탐색이니 이분탐색으로 하는 것을 추천드립니다.

import java.util.Arrays;
import java.util.Scanner;

/**
 * jhChoi - 201126
 * 백준 - 로봇 프로젝트
 */
public class Beak_RobotProject {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            long x = sc.nextInt() * 10000000;
            int n = sc.nextInt();
            int[] legoArr = new int[n];

            for (int i = 0; i < n; i++) {
                legoArr[i] = sc.nextInt();
            }

            Arrays.sort(legoArr);   //이진탐색을 위한 정렬

            int left = 0, right = legoArr.length - 1;

            while (left < right) {
                long sum = legoArr[left] + legoArr[right];

                if (sum == x) { //찾는 숫자인 경우
                    break;
                }

                if (sum < x) { //찾는 숫자보다 이전에 있는 경우
                    left++;
                } else {       //찾는 숫자보다 이후에 있는 경우
                    right--;
                }
            }

            if(left >= right){
                System.out.println("danger");
            }else{
                System.out.println(String.format("yes %d %d",legoArr[left],legoArr[right]));;
            }
        }
    }
}