문제

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

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 구멍의 너비 x가 주어진다.
다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다.
다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다.

---

출력

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

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

---

풀이

제한조건

• (1 ≤ x ≤ 20, x는 정수) 단위는 센티미터
• (0 ≤ n ≤ 1000000)
• ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

접근방법

투 포인터
정말 많이 틀렸다.
입력과 출력을 두 번 세 번 주의하자.

1. 입력
   여러개의 테스트 케이스로 구성되어 있다.
   하지만, 테스트 케이스가 몇 개인지 알려주지 않으며, 종료를 위한 입력이 별도로 없다.
   따라서 더 이상 입력이 없다면, 종료인것이다.
   Java에서 알고리즘을 풀면 Scanner 대신 BufferedReader를 사용하는데, BufferedReader를 사용한다면, 입력의 끝을 나타내는 eof를 확인할 수 있는 메소드가 별도로 없다.
   따라서 아래와 같이 입력을 받고 데이터를 확인하여 체크해야한다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = "";
while ((s = in.readLine()) != null) {
	// 입력을 우선 받고, null이면 추가 입력이 없는것 -> EOF
}

2. 투 포인터
   투 포인터를 생각하게된 이유는 문제의 조건에서 2개의 조각을 사용하기 때문이다.
   2개의 조각을 사용해서 조건을 검사하는 문제이기 때문에, 투 포인터를 사용한다면, 선형시간안에 모든 조각을 검사할 수 있다.

l1조각을 0에, l2조각을 n-1에서부터 시작하여 값을 조정하며 확인하면 된다.
만약 N이 2보다 작다면, 투 포인터로 탐색할 필요없이 조건에 따라 항상 불가능이다.

3. 출력
   몇 개인지 모를 테스트케이스에서 System.out.println으로 반복하여 출력하기에는 시간적 낭비가 크다.
   StringBuilder를 이용해서 기록해두고 한 번에 출력해주자.

---

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		int[] arr;
		StringBuilder sb = new StringBuilder();
		while ((s = in.readLine()) != null) {
			int x = stoi(s) * 10000000;
			int N = stoi(in.readLine());
			arr = new int[N];
			for (int i = 0; i < N; ++i)
				arr[i] = stoi(in.readLine());

			Arrays.sort(arr);

			// 투 포인터로 탐색
			if (N >= 2) {
				int l1 = 0;
				int l2 = N - 1;
				boolean flag = false;
				while (l1 < l2) {
					int sum = arr[l1] + arr[l2];
					if (sum == x) {
						sb.append("yes ").append(arr[l1]).append(" ").append(arr[l2]).append("\n");
						flag = true;
						break;
					} else if (sum < x) {
						l1++;
					} else {
						l2--;
					}
				}
				if (!flag)
					sb.append("danger\n");
			} else
				sb.append("danger\n");
		}
		System.out.println(sb);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}