satisfies() 안에서 매번 정렬 .sorted() 사용.sorted().limit(N) // 매번 degree 이하의 맥주들ㅇ르 전부 모아서 정렬
- -
satisfies(long degree)는 이분 탐색 내에서 수십 번 호출 - - 최악의 경우 O(K log K) 연산을 이분 탐색 반복 횟수만큼 계속
ex)
bearTreeMap.headMap(degree, true).values().stream()
.flatMap(Collection::stream)
.sorted()
- TreeMap이 주는 부분 리스트는 O(log K)로 잘 가져오지만,
.flatMap()이후 리스트를 합친 후.sorted()하면서 매번 O(K log K) 소비
시간 복잡도 분석 : satisfies() 내 .sorted() → O(K log K)
- 60번 반복하면 → 60 * K log K ≒ 시간 초과
매번 정렬 말고, 우선순위 큐(힙) 사용도 괜찮을 것 같습니다 :D
- 지금방식 : 모든 맥주를 다 보고 → 정렬해서 → 만족도 높은 맥주 N개 뽑음 → 합 계산
PriorityQueue(우선순위 큐)를 써서 지금까지 본 맥주 중 만족도 높은 순으로 N개만 저장 방식

jbw9964 1년 전
입력으로 주어진 도수 레벨 중 최댓값을 경계로, ( [1, MAXIMA] )
N 개의 맥주를 마실 수 있으면서 선호도 합이 M 이상인 간 레벨을 이분 탐색하였습니다.
특히 TreeMap 의 headMap 뷰로
특정 도수레벨 이하의 맥주 중, 최대 선호도를 가진 N 개의 맥주를 판별했습니다.
이 때 시간복잡도를 생각해보면 이분 탐색 자체는 log(MAXIMA) ( == log(2^31) ),
`satisfies` 메서드는 `sorted 정렬` + `선호도 합 게산` 으로 (K * log(K) + N) 이므로
최대 연산은 ( log(2^31) * ( 200,000 * log(200,000) + 200,000 ) ) ~= 10^7 라 판단했는데....
제출하니 1% 못가서 시간초과가 발생합니다.
어디를 잘못 생각한 걸까요...? ㅠㅠ