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% 못가서 시간초과가 발생합니다.

어디를 잘못 생각한 걸까요...? ㅠㅠ

bangsa100   1년 전

 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개만 저장 방식

댓글을 작성하려면 로그인해야 합니다.