[자바] 백준 2246 - 콘도 선정 (boj java)

문제 : boj2246

 

  각 N개에 대해 모든 N-1개의 다른 지점들을 전부 확인해봐도 O(N^2)으로 시간 제한인 2초 내에 가능하다. 따라서 모든 경우를 봐주면 된다. 문제에 제시된 조건을 if문으로 잘 표현만 할 수 있다면 어렵지 않게 풀 수 있다.

 

코드 : github

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

public class Main {
    class Condo {
        int d, c;
        public Condo(int d, int c) {
            this.d = d;
            this.c = c;
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Condo[] arr = new Condo[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Condo(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            Condo cur = arr[i];
            boolean chk = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (cur.c>arr[j].c && cur.d>=arr[j].d) {
                    chk = false;
                    break;
                }
                if (cur.d>arr[j].d && cur.c>=arr[j].c) {
                    chk = false;
                    break;
                }
            }
            if (chk) cnt++;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}