[정렬] BOJ_3649 로봇 프로젝트

문제

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

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

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

입력

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

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x가 주어진다. x의 단위는 센티미터이다.

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

다음 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ의 단위는 나노미터이다. 블럭의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

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

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

예제 입력 

1
4
9999998
1
2
9999999

예제 출력 

yes 1 9999999

코드

package sort;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
/**
 * https://www.acmicpc.net/problem/3649
 * 로봇 프로젝트
 * @author minjung
 */
public class baekjoon_3649 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        sc.init();
        String size = "";
        while ( (size = sc.readLine()) != null ){
            int size1 = Integer.parseInt(size);
            new baekjoon_3649().solve(size1);
        }
    }
    
    private void solve(int size) {
        
        int legoNum = sc.nextInt(); // 레고의 갯수
        int[] legoSize = new int[legoNum]; // 여러 크기의 레고를 담을 배열
        
        for( int i = 0; i < legoNum; i++ ){
            legoSize[i] = sc.nextInt();
        }
        
        size = size * 10000000; // 나노미터로 변경
        Arrays.sort(legoSize);
 
        int l1 = 0;
        int l2 = 0;
        boolean isOkay = false;
        
        int flagL = 0;
        int flagR = legoNum-1;
        
        int sum = 0;
        while ( flagL < flagR ){
            sum = legoSize[flagL] + legoSize[flagR];
            
            if( sum == size ) {
                l1 = legoSize[flagL];
                l2 = legoSize[flagR];
                isOkay = true;
                break;
            }
            else if ( sum < size ){
                flagL++;
            }
            else if ( sum > size ){
                flagR--;
            }
        }
        
        if ( l1 != 0 && l2 != 0) {
            System.out.printf("yes %d %d\n", l1, l2);
        }
        else {
            System.out.printf("danger\n");
        }
    }
    
    static class sc { 
        private static BufferedReader br;
        private static StringTokenizer st;
        
        static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
        
        static String readLine() {
            try{
                return br.readLine();
            } catch (IOException e){
                e.printStackTrace();
            }
            return null;
        }
        
        static String next() {
            while (!st.hasMoreTokens() ){
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        static int nextInt() {
            return Integer.parseInt(next());
        }
        
    }
}