2 분 소요

Heap

문제

문제 링크

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

입력

첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)

다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

출력

a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

예제 입력 1 복사

5 0 2 3 2 0 0 0

예제 출력 1 복사

-1 3 2 -1

스스로 고민

  • N 개의 선물을 줘야 할 사람이 있고 그다음에 0이 나온다면 선물을 한 개씩 나눠줘야 한다.
  • 선물을 갖고 있지 않다면 -1을 반환
  • 선물이 들어올 때는 첫 번째에 총 선물의 개수 그다음에는 각 선물의 값어치가 들어온다.

접근법

  • 최대 힙으로 풀어보자

    구현 코드

import heapq
import sys
n = int(sys.stdin.readline())
heap = []
heapq.heapify(heap)

for _ in range(n):
    k = list(map(int, sys.stdin.readline().split()))
    if k[0] == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(-1)
            
    else:
        for i in range(k[0]):
            heapq.heappush(heap, -k[i+1])

시간 복잡도와 공간 복잡도

시간 복잡도:

  1. 빈 힙(heap)을 초기화하는 부분: heapq.heapify(heap)는 O(1) 시간이 소요
  2. 표준 입력에서 입력 값을 읽는 부분: n = int(sys.stdin.readline())은 O(1) 시간이 소요
  3. n번 반복하는 루프: for 루프인 for _ in range(n)은 n번 실행

루프 내부:

  • 입력 값을 리스트 k로 읽어오는 부분: k = list(map(int, sys.stdin.readline().split()))은 O(k[0]) 시간이 걸린다. 여기서 k[0]는 리스트의 첫 번째 요소로, 리스트 내 요소의 개수를 나타낸다.
  • k[0]이 0인지 확인하는 부분: 이 부분은 상수 시간이 소요된다.
  • 만약 k[0]이 0이 아니라면, 루프 내에서 요소를 힙에 넣는 작업이 발생한다. 이 루프는 k[0]번 실행된다.

따라서 전체 시간 복잡도는 O(n * k[0]) 다.

공간 복잡도:
공간 복잡도는 주로 사용하는 데이터 구조에 의해 결정된다.
입력으로 주어지는 값들을 힙에 저장하고 팝하는데 사용되며, 이러한 데이터는 메모리에 저장된다. 힙의 크기는 입력 값에 따라 변하기 때문에 공간 복잡도는 입력 값과 힙에 저장된 요소들에 따라 달라진다. 일반적으로 입력 값과 힙의 크기에 비례한 공간이 소요된다.

코드 전체의 공간 복잡도는 O(n * k[0])이 될 수 있다.

회고 과정

  • readline() 이 3, 4, 5 이렇게 들어올 때 계속 오류가 나서 좀 고생했다.
  • 그냥 sys.stdin.readline().split() 로 받을 경우 리스트가 str로 되고 다시 반복문으로 int로 형 변환을 해줘야 하는데 map을 이용하면 좀 더 편하게 이용 가능하다

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

다른 사람들 코드도 비슷비슷하다. 다만 공백 처리를 할 때 오른쪽 기준 공백을 rstrip() 을 사용해서 좀 더 확실하게 처리하는 걸 알게 되었다.

댓글남기기

참고