[이코테 Ch14-25] 실패율 (정렬)

👩🏻‍💻문제설명

[이코테 Ch14-25] 실패율 (정렬)

 

✍️Idea Sketch

문제요약

실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하라.

 

 

 

시간복잡도

스테이지의 개수 N은 500 이하이고, stages의 길이는 200,000 이하이다. 500 x 200,000는 1억이기 때문에 시간초과가 날 것이라 예상했다. 하지만 시간초과가 나지 않았다. 스테이지에 도달한 플레이어의 수가 0명인 경우, count()를 하지 않는다. 이 점 때문에 통과했다고 생각한다.

 

a.count(x)
리스트 a에서 x가 몇개 있는지 count한다. count하기 위해 리스트 a를 전체 탐색 해야 하므로 시간복잡도는 O(n)이다. stages.count()는 리스트 stages를 전체 탐색한다.

 

sort(), sorted()
파이썬은 기본 정렬 라이브러리인 sorted()와 sort()함수를 제공한다. 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적인 경우 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(nlogn)을 보장한다.

 

 

 

 

알고리즘 : 정렬

 

 

 

 

✍️내 소스코드

• clear : 스테이지에 도달한 플레이어 수
• 스테이지에 도달한 플레이어 수가 0명인 경우, 실패율은 0이다.
• 스테이지에 도달한 플레이어 수가 1명 이상인 경우, 아직 클리어하지 못한 플레이어의 수를 count 한다.
• clear를 갱신한다. 지금 스테이지를 클리어하지 못한 플레이어는 다음 스테이지에 도달했을리 만무하다.

 

 

전체 코드

  def solution(N, stages):
      queue = []
      clear = len(stages)

      for stage in range(1, N+1):
          if clear == 0:
              queue.append((0, stage))
          else:
              fail = stages.count(stage)
              queue.append((fail / clear, stage))
              clear -= fail

      queue.sort(key = lambda x: -x[0]) 
      return [queue[i][1] for i in range(N)]