[JAVA] 백준 3649번 : 로봇 프로젝트

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

---

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

public class Main {
    static String input = null;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while ((input = br.readLine()) != null) {
            int x = Integer.parseInt(input) * 10000000;
            int N = Integer.parseInt(br.readLine());
            if (N == 0) {
                sb.append("danger").append("\n");
                continue;
            }
            int[] lego = new int[N];
            for (int i = 0; i < N; i++) {
                lego[i] = Integer.parseInt(br.readLine());
            }

            Arrays.sort(lego);

            String answer = "danger";
            int left = 0, right = N - 1;
            while (left < right) {
                if (lego[left] + lego[right] < x) {
                    left++;
                } else if (lego[left] + lego[right] > x)
                    right--;
                else {
                    answer = "yes " + lego[left] + " " + lego[right];
                    break;
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

💡 투포인터

풀이

• 문제 조건을 잘 살펴볼 것! 테스트 케이스가 여러개 주어질 수 있다... !
  • 더이상 입력이 없으면 테스트케이스가 종료된 것!

💡 br.readline() != null 로 입력 조건을 걸어줬다
- 만약 종료 조건이 0과 같은 별도의 문자열로 주어진다면, equals를 활용해야한다 (등호로 하면 NullPointer 에러)
  e.g. while(!(input = br.readLine()).equals("0")) 이렇게!!

• 처음 풀이에서는 정렬 + Set을 활용해 풀려고 시도했다
  • lego를 정렬한 뒤, 앞에서부터 탐색해서 x - lego[i] 가 set에 존재하는지 탐색함
  • 존재한다면 바로 break 하고 다음으로 넘어가도록 (차이가 제일 클 테니)
  • 하지만 25%에서 틀렸습니다 발생... 반례를 생각해보니 동일한 크기의 레고가 안들어온다는 보장이 없음 -> set 안됨
    • 반례) x = 20 이고, 레고가 10, 10 들어오는 경우
• 대안 >> 투포인터를 활용해 풀었다. 마찬가지로 정렬한 뒤, 양 끝(left, right)에서 시작해 각각 하나씩 전진하며 조건이 맞으면 탈출하는 방식으로..
  
  • left번째 레고 + right번째 레고 < x 인 경우 : 작은 레고(왼쪽)의 크기를 키워야 함
  • left번째 레고 + right번째 레고 > x 인 경우 : 큰 레고(오른쪽)의 크기를 줄여야 함
  • left번째 레고 + right번째 레고 = x 인 경우 : 지금이 최선의 경우이므로 출력하고 바로 탈출.