백준 2246번 문제를 풀어보았다☆ with java

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		TreeMap<Integer,Integer> map = new TreeMap<>();
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		for (int i = 0; i < N; i++) {
			int D = sc.nextInt(); int C = sc.nextInt(); //가격
			if(map.containsKey(C)) {
				if(map.get(C)<D) {
					continue;
				}
			}
			map.put(C,D); // 가격을 key로 오름차순으로 정리.
			
		}

		int count = 0;
		while(map.size()>0) {
			count++;
			Integer [] key = map.keySet().toArray(new Integer[0]);
			Integer close = map.get(map.firstKey());
			for(Integer i:key) {
				if(map.get(i)>=close) {
					map.remove(i);
				}
			}
		}
		System.out.println(count);
	}
	


}

---

<문제이해>

일단 이 문제는 가장적합한 콘도를 구하는 것이다. 

 

조건을 주목해야 한다. 만약 우리가 가장 가격이 낮은 콘도를 기준으로 판별한다면 문제는 쉽게 풀린다. 만약 '가장' 가격이 낮은 콘도보다 멀리 있다면 조건2번을 위반하게 된다. 따라서 이 콘도들은 후보에서 삭제 된다. 따라서 그것들과 기준이 되었던 가장 낮은 콘도까지 없앤다. (Count ++ )그러면 남은 콘도 후보들이 생긴다. 이것들을 가지고 콘도들이 전부 사라질 때까지 반복한다.

---

코드 풀이.

 

나는 이것을 TreeMap을 이용해서 풀었다. 이것은 키와 값을 입력하면 키의 값에 따라 오름차순으로 정렬시키는 것이다. 따라서 firstKey()을 이용한다면 가장 가격이 낮은 콘도를 알수 있다. 

여기서 주의할 점은 TreeMap를 이용한다면 이것은 key 중복이 허용되지 않기 때문에 입력과정에서 이것을 알맞게 처리해줘야 한다. (Key가 같다는 것은 cost 가 같다는 것이다. 따라서 거리가 가장 가까운 것이 채택되어야 한다.)

이것이 처리되었다면 이제 거리가 먼것을 remove로 지워줬다.

---

후기.

 

일단 풀긴풀었는데 시간이 개많이 나가는 개쓰레기 코드가 탄생했다! 왜인지 모름,,

(언젠가 시간 복잡도랑 자바 개념 그리고 stringbuffer 공부도 해야하는데 계속 미루는중 으어억)

그나저나 추석이라 외가에 왔는데 시간이 개많다! 할것이 없는거시다....

 

Ps,,안풀릴줄 알았는데 의외로 풀려서 매우 기쁘다😊