[백준] 2246번: 콘도 선정(구현)

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

2246번: 콘도 선정

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int N = Integer.parseInt(bf.readLine()); // 콘도의 갯수
		int[][] arr = new int[N][2];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());	// 바닷가로부터 거리
			arr[i][1] = Integer.parseInt(st.nextToken());	// 숙박비
		}
		
		int count = 0;	// 후보 콘도의 갯수
		
		/* 
		 * 조건 1) X보다 가까우면 X보다 숙박비가 더 비싸다
		 * 조건 2) X보다 숙박비가 비싸면 X보다 더 멀다. 
		 */
		for(int i=0; i<N; i++) {
			boolean flag = true;
			for(int j=0; j<N; j++) {
				
				// 자기 자신은 비교 X
				if(i == j)
					continue;
				
				if(arr[i][0] >= arr[j][0]) {	 // i번째를 X라고 판단할때, X보다 더 가까울때
					if(arr[i][1] >= arr[j][1]) { // X가 더 멀리있는데 X가 숙박비가 더 비쌀때
						flag = false;
						continue;
					}
				}
				
				if(arr[i][1] >= arr[j][1]) {	 // X보다 숙박비가 저렴할때
					if(arr[i][0] >= arr[j][0]) { // X보다 저렴한데 X보다 가까이 있을때 
						flag = false;
						continue;
					}
				}
			}
			if(flag)
				count ++;
		}
		
		bw.write(count + "\n");
		bw.flush();
		bf.close();
		bw.close();
	}

}

풀이

뭔가 헷갈렸는데 문제에서 주어진 조건 2가지 모두 속할때, 콘도 X는 후보가 된다.

  1. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다.

  2. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다.

N의 최대범위가 10,000 이므로 완전 탐색으로 해도 시간초과가 발생하지 않을거라 생각하고 완전 탐색으로 해결했다.

O(N^2)

 

풀이는 모든 콘도들을 탐색하면서 X보다 더 가까운 콘도지만 X보다 숙박비가 더 저렴할경우

 -> 1번 조건을 만족하지 않으므로 flag = false

 

또한 모든 콘도들을 탐색하면서 X보다 숙박비가 저렴한데 X보다 가까운경우

 -> 2번 조건을 만족하지 않으므로 flag = false

 

위 조건을 통해 flag 값이 true면 후보 콘도이므로 +1씩 해준다.

 

시간이 너무 오래걸려서 다른 정답 코드들을 보면서 생각해보니 다른 콘도들과 비교하면서 1번 조건이나 2번 조건을 만족하지 않는경우, 다른 콘도들은 볼 필요도 없이 그 콘도들은 후보 콘도에서 제외된다.

따라서 continue가 아닌 break를 통해 제출하니 2배 가량 시간이 줄어들었다.

				if(arr[i][0] >= arr[j][0]) {	 // i번째를 X라고 판단할때, X보다 더 가까울때
					if(arr[i][1] >= arr[j][1]) { // X가 더 멀리있는데 X가 숙박비가 더 비쌀때
						flag = false;
                        			// continue;
						break;
					}
				}
				
				if(arr[i][1] >= arr[j][1]) {	 // X보다 숙박비가 저렴할때
					if(arr[i][0] >= arr[j][0]) { // X보다 저렴한데 X보다 가까이 있을때 
						flag = false;
                        			// continue;
						break;
					}
				}