JinWoo Kim

백문이 불여일견, 백견이 불여일행.

2 minute read

1. 팩토리얼 0의 개수

  • 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

    1. 배열에 자연수 x를 넣는다.
    2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

  • 프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

  • 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
  • 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
  • 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
  • x는 $2^{31}$보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

  • 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

풀이

import sys
import heapq


arr = []
for _ in range(0,int(sys.stdin.readline())):
    x = int(sys.stdin.readline())
    if x > 0:
        heapq.heappush(arr,x)
    else:
        if arr:
            print(heapq.heappop(arr))
        else:
            print(0)

채점 결과

  • 정답

리뷰

  • heapq에서 제공하는 기본 힙은 최소힙이므로, 활용하여 풀었다.

2. 듣보잡

  • 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다.
  • 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.
  • 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다.

  • N, M은 500,000 이하의 자연수이다.

  • 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

  • 듣보잡의 수와 그 명단을 사전순으로 출력한다.

풀이

import sys

N,M = list(map(int,sys.stdin.readline().split()))

dic = {}
arr = []
for _ in range(0,N):
    name = sys.stdin.readline().strip('\n')
    if name not in dic.keys():
        dic[name] = 0

for _ in range(0,M):
    name = sys.stdin.readline().strip('\n')
    if name in dic.keys():
        arr.append(name)

print(len(arr))
[print(x) for x in sorted(arr)]

채점 결과

  • 정답

리뷰

  • 듣도 못한 인간과 보도 못한 인간의 교집합을 구하는 문제로 생각하면 될것같다.

  • 듣도 못한 인간을 딕셔너리에 넣고, 보도 못한 인간이 그 안에 있으면 따로 배열에 저장한다.

  • 배열의 길이와 배열의 내용을 출력한다

  • 배열의 내용을 출력할때 시험삼아 print문을 list comprehension안에 넣어서 굴려봤는데, 기대한대로 깔끔하게 작동해줘서 만족스러웠다.

더 나은 풀이

import sys
n, m = map(int, input().split())
nameList = sys.stdin.read().splitlines()
hearset = set(nameList[:n])
seeset = set(nameList[n:])
ret = list(hearset & seeset)
ret.sort()
print(len(ret))
for i in ret:
    print(i)

더 나은 풀이 해설

  • 처음 내가 제시했던것처럼, 두 집합의 교집합을 구하는 방법을 사용했다.

  • set을 통해 듣도못한/보도못한 집합의 중복을 제거한다.

  • list(hearset & seeset)을 통해 중복되는 요소만 뽑아낸다.

  • 사전순으로 출력해야 하므로, 한번 정렬해주고 리스트의 길이와 내용을 출력해준다.

You May Also Enjoy