보석 도둑
-
[백준 1202번] 보석 도둑(Java 풀이)Algorithm/Greedy Algorithm 2022. 2. 28. 16:47
백준알고리즘 1202번 : 보석 도둑 시간 초과와 RunTime Error를 반복한 끝에 성공했다. 우선순위큐(Priority Queue)의 중요성을 배운 문제이다. 이중for문(혹은 for문과 while문)을 사용하게 된다면 최대 30만*30만의 시간복잡도가 발생하게된다. 따라서 가방의 최대 무게외 보석의 정보 배열을 정렬했다고 하더라도 시간 제한이 걸리는 testCase가 발생하기 때문에.. 이 방식은 한 번 해보고 빠르게 접었다. 우선순위큐의 장점은, 내가 add한 Queue 중 최대값(혹은 최소값)을 poll할 수 있다는 점이다. 이는 인자들을 꾸준히 더하거나 빼야하는 상황이나 (특정 가방이 들수 있는 보석들을 모두 담고, 하나의 보석만 빼고 남겨둬야한다.) 인자들의 최대, 최소값을 구해야하는 상..