0. 기본 정보

0-A. 개요

python/백준 - 14919번 문제에 대한 분석임.

0-B. 문제 정보

백준 - 14919번: 분포표 만들기

---

1. 정답 코드

import heapq as h


n = int(input())
list_ = list(map(float, input().split()))
list_.sort()

answer = []
for i in range(1, n + 1):
    
    m = round((1/n) * i, 7)
    while True:
        if list_:
            t = h.heappop(list_)            
        else:
            print(len(answer), end=' ')
            answer = []
            break
        
        if t < m:
            h.heappush(answer, t)
        elif t >= m:
            h.heappush(list_, t)
            print(len(answer), end=' ')
            answer = []
            break

---

2. 핵심풀이

1. 완전탐색으로 풀 경우 최악의 경우 10^3 * 10^6 을 계산해야하므로 python으로는 무조건 시간초과
2. 최소힙을 활용하면 실수 a의 list 길이 만큼만 연산을 하므로 시간초과를 해결할 수 있음.
3. 실수 a의 list에서 최소값을 빼낸 다음 구간을 나누는 값 m과 비교하여
   m보다 작을 경우 힙에 넣고 m보다 클 경우 지금까지 넣은 힙의 길이를 출력한다.
   
   

2-a. 코드 분석

import heapq as h


n = int(input())
list_ = list(map(float, input().split()))
list_.sort()

• 문제풀이에 필요한 입력값을 변수에 삽입
• 실수 a의 모음인 list_변수를 오름차순으로 정렬.
  • heapify 메소드를 써도 되지만 시간복잡도 평균은 list.sort()가 더 빠르다.

answer = []
for i in range(1, n + 1):
    
    m = round((1/n) * i, 7)

• 힙으로 활용할 answer list 선언
• 이제부터 for문 반복을 활용함. 이때 각 반복마다 구간을 나눌 기준값인 m을 선언.
  • 이때 부동소수점을 방지하기 위해서 round 함수를 활용해준다.
  • 단, 문제에서 실수는 소수점 6자리 까지 표기한다고 하여 round의 인자값으로 6을 보내면 문제가 틀리게 된다.
    이유는 round 함수의 반환값은 가까운 짝수를 반환하기 때문! 우리가 아는 그 반올림이 아니다. 이 링크에서 2-a 참고
    
    round(2.5)는 3이 아닌 2를 반환한다.
    이런 이유로 round인자값으로 7을 넣어준다.

    while True:
            if list_:
                t = h.heappop(list_)            
            else:
                print(len(answer), end=' ')
                answer = []
                break

• for문 안에 while문을 쓴다.
  (이중 반복문이라 해도 결국 list_만 순회하므로 시간복잡도가 커지지 않는다.)
• 만약 list_가 빈 리스트가 아니라면 heappop을 통해 최소값을 추출하여 t에 넣어준다.
• 만약 list_가 빈 리스트라면 더이상 추출할 최소값이 없으므로
  (list_의 순회를 마쳤으므로)
  값들을 보관하고 있는 answer 힙의 길이를 출력하고
  while문 반복을 종료한다.
  • 여기서 answer를 비워주는 이유는 첫 구간에 모든 값이 다 들어갈 경우 이후 구간에는 0이 출력되어야 하지만 answer를 비워주지 않아서 answer길이의 값이 출력된다.
    ex)

    3
    0.1 0.1 0.1 0.1
    >> 4 4 4 4

        if t < m:
            h.heappush(answer, t)
        elif t >= m:
            h.heappush(list_, t)
            print(len(answer), end=' ')
            answer = []
            break

• 위에서 최소값을 추출하여 선언한 변수 t가 구간을 나눌 기준값인 m보다 작다면 answer힙에 값을 넣는다.
• list_에서 추출한 최소값t가 구간을 나누는 기준값인 m보다 같거나 크다면
  이전까지 answer에 들어간 값들이 한 구간임을 의미하므로
  t는 다시금 list_에 넣고 answer의 길이를 출력한 뒤
  answer를 비워준다.(다시 다음 구간 수를 넣어야하기 때문)