[PS] BOJ 29714 / 브실이의 구슬 아이스크림

Minjun Kim

16 May 2025 • 2 min read

문제 링크: https://www.acmicpc.net/problem/29714

Thumbnail: Photo by Elza Kurbanova (Unsplash)

여러분은 어떤 아이스크림을 좋아하시나요? 저는 메로나를 제일 좋아합니다 😄

풀이

태그에 해시를 이용한 집합과 맵이 있듯이, Map 자료구조를 이용하면 간단히 풀이할 수 있습니다. 기본적인 원리는 "각 아이스크림 구슬이 몇 개 있는지 파악하자" 입니다. 저는 파이썬의 내장 객체인 dict를 활용했습니다.

먼저, 초기 입력으로 주어진 아이스크림을 구슬의 색깔을 키, 구슬의 개수를 값으로 하는 맵 자료구조 형태로 저장합니다. 이 Map은 ICE_CREAM이라고 부르겠습니다.

이후 매 차례 아이스크림을 먹을 때 마다, \(A_i\)를 동일한 방식으로 Map에 정리합니다. 이후, ICE_CREAM이 \(A_i\)에 저장된 각 아이스크림 구슬을 같거나 더 많이 가지고 있는지 비교합니다. 다 가지고 있다면, ICE_CREAM에서 \(A_i\)을 뺀 뒤, \(B_i\)를 더해줍니다.

위 과정을 모두 반복한 뒤, 출력에서는 ICE_CREAM의 각 키를 자신의 값만큼 반복해서 출력해주면 됩니다.

전체 코드

input = open(0).readline
N = int(input())
ICE_CREAM = {}
for ice in map(int, input().split()):
    try:
        ICE_CREAM[ice] += 1
    except KeyError:
        ICE_CREAM[ice] = 1

Q = int(input())
for _ in range(Q):
    a_i, *A = map(int, input().split())
    b_i, *B = map(int, input().split())
    a = {}
    for ice in A:
        try:
            a[ice] += 1
        except KeyError:
            a[ice] = 1
    if all(ICE_CREAM.get(ice, 0) >= a[ice] for ice in a): # 모든 아이스크림이 존재하는지 확인
        for ice in a:
            ICE_CREAM[ice] -= a[ice]
            if ICE_CREAM[ice] == 0:
                del ICE_CREAM[ice]
        for ice in B:
            try:
                ICE_CREAM[ice] += 1
            except KeyError:
                ICE_CREAM[ice] = 1

res = []
for ice in ICE_CREAM:
    for _ in range(ICE_CREAM[ice]):
        res.append(str(ice))
print(len(res))
if ICE_CREAM:
    print(" ".join(res))

solution.py