(JAVA) 백준 1202번 : 보석 도둑

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

1202번: 보석 도둑

 

후..

 

나에겐 시간 도둑인 문제였다.

 

 

상당히 헤맸어...

 

정답률 23%인 이유가 있었다.

 

 

처음에 

 

가방 무게 작은 순서대로 하나씩 꺼내서

그 가방보다 같거나 작은 모든 보석들을 가격 순으로 정렬한 후

가장 큰 가격을 가방에 넣는다.

 

의 흐름은 맞았지만

시간복잡도가 결국에는 O(가방 개수 * 보석 개수) 이상으로 가기 때문에

 

당연히 시간 초과가 발생했다.

 

 

 

힌트를 살짝 얻기 위해 

 

구글링을 한 결과

 

흐름은 맞았고, 저기서 시간을 줄일 수 있는 대안책을 찾았다.

 

바로 

 

PriorityQueue!! ( 왜 생각 못했을까 .. )

 

 

굳이 가격 순으로 정렬할 필요 없이

 

별도의 우선순위 큐 보석함을 만들어

현재 가방보다 무게가 같거나 작은 보석들을 넣어두면 되지 않겠는가?!

 

어차피 우선순위 큐에 넣는 순간 

Comparable 인터페이스에 의해 자동 정렬되서 나오는 것을...

 

게다가 Queue이기 때문에

삽입 삭제 시 O(1)의 시간복잡도가 들어서

 

O(가방 개수 * 보석 개수) -> O(가방 개수 + 보석 개수) 급으로 낮출 수 있다...

 

 

 

여기서 계속 런타임 에러가 발생했는데...

 

코드는 맞는데 계속 뜨길래

 

직접 콘테스트 페이지까지 가서 테스트케이스를 전부 돌려봤다.

 

그 결과..

 

 

Comparison mComparison method violates its general contract!

**이 문제는 별도의 포스트에서 다뤄보겠다.

https://maivve.tistory.com/78

(JAVA) java.lang.IllegalArgumentException: Comparison method violates its general contract! 에러 해결

 

 

 

 

아무튼

 

되게 사소한 것 하나로 한 시간은 더 잡아먹었다.

 

매커니즘

---

 

가방에는 최대 1개의 보석만 담을 수 있기 때문에

 

최고의 가격을 얻기 위해서는

 

 

가장 작은 무게의 가방에

그 무게보다 같거나 작은 보석들 중 가장 큰 가격의 보석을 담는다.

 

 

이 문장만 기억하면 끝이다.

 

풀이 방법이 보이는가?

 

 

 

1) 가방 담은 배열 무게 오름차순 정렬

 

2) 보석 담은 배열(또는 ArrayList. 무게와 가격을 담은 별도의 객체) 무게 오름차순 정렬

*** 이 때, Collections.sort() 안에 Comparator를 생성해도 되고, Array인 경우에는 보석 클래스에서 Comparable 인터페이스를 implements해도 된다.

 

3) 가방 작은 무게부터 하나씩 탐색

 

4) 보석들도 작은 무게부터 탐색하면서 선택한 가방의 무게보다 같거나 작은 보석들을 우선순위 큐에 집어넣는다. (가격만 넣어도 상관없음)

*** 중요한 것은 인덱스도 같이 증가시키고 이 인덱스를 별도로 저장해놔야 한다.

 

5) 다 넣었으면, 우선순위 큐에서 가장 큰 가격을 꺼내 전체 가격에 더해준다.

 

 

참고로,

우선순위 큐 타입으로 Integer를 사용했기 때문에

낮은 값부터 반환해주는 특성을 고려해서

 

넣을 때는 - 를 붙여서 음수로 넣고,

꺼내고 나서는 Math.abs() 로 절댓값으로 사용했다.

 

 

 

 

후..

감사합니다.

 

소스코드

---

 

 

 

참고

https://dundung.tistory.com/88