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

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

3649번: 로봇 프로젝트

 

---

블럭길이를 오름차순 정렬 한 후에

1개의 블럭을 뽑고, 이 블럭과 합쳐서 구멍을 완벽하게 메꿀 수 있는 블럭이 존재하면

답을 출력하는 방식으로 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;

public class P3649 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			while (true) {

				boolean flag=false;
				int x = Integer.parseInt(br.readLine());
				x = x * 10000000;
				int n = Integer.parseInt(br.readLine());

				LinkedList<Integer> list = new LinkedList<>();

				for (int i = 0; i < n; i++) {
					list.add(Integer.parseInt(br.readLine()));
				}

				Collections.sort(list);

				while (!list.isEmpty() && list.peek() <= x / 2) {
					int now = list.poll();
					if (list.contains(x - now)) {
						System.out.println("yes " + now + " " + (x - now));
						flag=true;
						break;
					}
				}
				if(!flag)
					System.out.println("danger");
			}
		} catch (Exception e) {
			System.out.println();
		}
	}
}

contains메소드가 시간복잡도O(n)인데 

아마 이것때문에 시간초과가 난 것 같다.

 

그래서 조금 다른 방법으로 다시 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

public class P3649 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			while (true) {

				int x = Integer.parseInt(br.readLine());
				x = x * 10000000;
				int n = Integer.parseInt(br.readLine());
				boolean flag=false;
				ArrayList<Integer> list = new ArrayList<>();

				for (int i = 0; i < n; i++) {
					list.add(Integer.parseInt(br.readLine()));
				}

				Collections.sort(list);

				int i = 0, j = n - 1;
				while (i < j) {
					int sum = list.get(i) + list.get(j);

					if (sum == x) {
						flag=true;
						break;
					} else if (sum > x) {
						j--;
					} else {
						i++;
					}
				}

				if (!flag) {
					System.out.println("danger");
				} else {
					System.out.println("yes " + list.get(i) + " " + list.get(j));
				}
			}
		} catch (Exception e) {
			System.out.println();
		}
	}
}

배열의 양 쪽에서 시작하는 i,j를 가지고

list[i]+list[j]이면 반복 중단,

합이 x보다 크면 j감소

합이 x보다 작으면 i증가 시킨다.

 

.

.

마지막 if문에 flag를 사용하지 않고

i==j일 때 danger을 출력하게 하고싶었다.

(while문을 계속 돌고, 답을 끝까지 못찾으면 i==j가 될 것이라 생각했다)

 

하지만 계속 답이 틀렸다고 나와서

flag를 추가해서 if문에 사용해봤는데 바로 정답처리 됐다....

 

왜 flag를 사용해야만 했을까?