#2246 : 콘도 선정

풀이방법

사용된 것:

정렬

브루트포스

Comparator Overriding

 

 

 

 

 

2022.11.17

 

콘도 X가 후보가 될 수 있는 조건은 다음과 같다.

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

거리 순으로 정렬한 후에 1번 조건을 체크하고,

가격 순으로 정렬한 후에 2번 조건을 체크한 후,

두 번의 체크 과정에서 한 번도 탈락하지 않은 콘도들의 개수를 세면 된다.

 

다음과 같은 방법으로 구현하였다.

 

1. Condo 클래스 정의

각각의 콘도는 Condo 객체로 저장된다.

Condo 객체는 다음의 3가지 필드를 가진다.

바닷가로부터의 거리 d, 숙박비 c, 후보가 될 자격을 나타내는 boolean 타입 변수 check

check의 초기값은 true이며, 후보 조건에 부합하지 못함이 발견되면 즉시 false로 값을 바꾸는 식이다.

 

2. 1번 조건 체크

콘도들을 거리 순으로 오름차순 정렬하고

모든 콘도 c에 대하여

c보다 거리가 가까운 놈들 즉 c보다 앞 순서인 놈들 중 c보다 숙박비가 싸거나 같은 놈이 하나라도 있다면 c의 check를 false로 바꾼다.

 

3. 2번 조건 체크

콘도들을 숙박비 순으로 오름차순 정렬하고

모든 콘도 c에 대하여

c보다 숙박비가 싼 놈들 즉 c보다 앞 순서인 놈들 중 c보다 바닷가로부터의 거리가 가깝거나 같은 놈이 하나라도 있다면 c의 check를 false로 바꾼다.

 

4. 정답 출력

check가 true인 콘도들의 개수를 화면에 출력한다. 

 

코드

Java(2022.11.16)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		Condo[] condoes = new Condo[n];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			condoes[i] = new Condo(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		//거리 순으로 오름차순 정렬하는 Comparator
		Comparator<Condo> cpd = new Comparator<Condo>() {
			@Override
			public int compare (Condo c1, Condo c2) {
				if(c1.getD() > c2.getD()) return 1;
				else if (c1.getD() == c2.getD()) {
					if(c1.getC() < c2.getC()) return 1;
					else return -1;
				}
				else return -1;
			}
		};
		
		//가격 순으로 오름차순 정렬하는 Comparator
		Comparator<Condo> cpc = new Comparator<Condo>() {
			@Override
			public int compare(Condo c1, Condo c2) {
				if(c1.getC() > c2.getC()) return 1;
				else if(c1.getC() == c2.getC()) {
					if(c1.getD() < c2.getD()) return 1;
					else return -1;
				}
				else return -1;
			}
		};
		
		//거리 순으로 오름차순 정렬
		Arrays.sort(condoes, cpd);
		
		//모든 콘도에 대하여, 나보다 바닷가에 가까운 콘도 중 가격이 더 싸거나 같은 것이 있는지 판단
		for(int i=0; i<n; i++) {
			for(int j=0; j<i; j++) {
				if (condoes[i].getC()>=condoes[j].getC()) {
					condoes[i].setCheck(false);
					break;
					}
			}
		}
		
		
		//가격 순으로 오름차순 정렬
		Arrays.sort(condoes, cpc);
		
		//모든 콘도에 대하여, 나보다 싼 콘도 중 거리가 바닷가에 가깝거나 같은 것이 있는지 판단
		for(int i=0; i<n; i++) {
			for(int j=0; j<i; j++) {
				if (condoes[i].getD() >= condoes[j].getD()) {
					condoes[i].setCheck(false);
					break;
				}
			}
		}

		
		int answer = 0;
		for(Condo c: condoes) {
			if(c.getCheck()) answer++;
		}
		
		System.out.print(answer);
	}

}

class Condo {
	private int d;	//거리
	private int c;	//가격
	private boolean check;	//false가 되면 후보 탈락
	public Condo(int d, int c) {
		this.d = d;
		this.c = c;
		this.check = true;
	}
	public int getD() {return d;}
	public int getC() {return c;}
	public void setCheck(boolean check) {this.check = check;}
	public boolean getCheck() {return check;}
}