[Python] 27914: 브실이의 구슬 아이스크림

🔗 문제 링크

29714번: 브실이의 구슬 아이스크림

💊 문제 요약

브실이는 요상하게 구슬 아이스크림을 먹는다. 첫 줄에 초기 아이스크림 구슬의 갯수 N이 주어지고, 둘째 줄에 N개의 구슬 숫자들이 공백으로 분리되어 주어진다.
셋째 줄에 입력되는 Q번의 구슬 아이스크림을 먹고 보충하거나, 아무것도 하지 않는 과정을 거쳐 구슬 아이스크림을 먹는다. (정말 요상하다.) Q번 두 개의 줄이 세트로 입력된다. 첫 번째 줄은, 먹으려는 아이스크림 구슬의 갯수와 그 갯수만큼 구슬의 숫자가 주어진다. 두 번째 줄은, 보충하려는 아이스크림 구슬의 갯수와 그 갯수만큼 구슬의 숫자가 주어진다.
만약, 먹으려는 아이스크림 구슬 중, 가지고 있는 아이스크림에 없는 것이 있다면 먹거나 보충하지 않고 넘어간다.

구슬 아이스크림을 다 먹은 후, 남아있는 아이스크림 구슬의 갯수와, 구슬의 숫자들을 공백으로 구분하여 출력하라. 

🌿 풀이 설명

정말 요상하고 기이한 문제 내용으로, 이해하는 데에 다소 어려움이 있을 수 있는 문제였다.

정답 코드

import sys
input=sys.stdin.readline

N=int(input().rstrip())
marbles_list=list(map(int, input().rstrip().split()))
marbles={}
for i in range(N):
    if marbles_list[i] in marbles.keys():
        marbles[marbles_list[i]]+=1
    else:
        marbles[marbles_list[i]]=1

Q=int(input().rstrip())
continue_std=True
for _ in range(Q):
    eatable=True
    ai, *Ai=map(int, input().rstrip().split())
    bi, *Bi=map(int, input().rstrip().split())
    a_dict={}
    for a in Ai:
        if a not in a_dict.keys():
            a_dict[a]=1
        else:
            a_dict[a]+=1

    for a in a_dict.keys():
        if a not in marbles.keys() or marbles[a]<a_dict[a]:
            eatable=False
            break

    if eatable:
        for a in a_dict.keys():
            marbles[a]-=a_dict[a]
        
        for b in Bi:
            if b not in marbles.keys():
                marbles[b]=1
            else:
                marbles[b]+=1

print(sum(marbles.values()))
for key, value in marbles.items():
    for _ in range(value):
        print(key, end=" ")

1. dictionary를 사용해야 하는 이유

우선 떠올려야 하는 개념은 아이스크림의 구슬을 담을 때 여러 자료 구조 중, dictionary를 사용해야 한다는 것이다.

list.pop(index)나 list.insert(index, value)는 시간 복잡도가 O(N)이기도 하고, 구슬 숫자에 제한 조건이 없어서 list를 사용하면 메모리, 시간적으로 매우 비효율적이다.

 

따라서, {marble_num: marble_count} 형태로 구슬 정보를 저장하고 구슬 아이스크림을 먹고 보충할 때에 각각의 구슬 숫자에 대응하는 key의 value를 더하고 빼며 정보를 업데이트하는 것이 중요하다. 이 때, key를 통해 해당하는 value 값을 조회하거나 업데이트하는 것의 시간 복잡도는 O(1)이다.

 

이처럼 dictionary가 적은 시간 복잡도를 가질 수 있는 이유는 dictionary가 hash 구조이기 때문이다.

각각의 key값은 해쉬 함수를 통해 특정한 index 값으로 mapping되고, 이를 통해 공간 효율성을 다소 포기하고 시간 효율성을 크게 높인다.

해쉬 구조의 작동 원리

 

(참고 포스팅: 파이썬의 딕셔너리는 어떻게 구현되어 있을까? -해시-)

2. 구현한 알고리즘의 시간 효율성 개선: 시간 복잡도 추정하기

초기 작성했던 코드는 시간 초과로 계속해서 오답 처리가 되었다.

dict.keys()를 따로 list로 관리해보는 것과 같이 크게 의미없는 코드 수정을 하다가, 아래의 정답 포스팅을 통해 코드의 문제점을 깨닫고 개선할 수 있었다.

 

[백준 알고리즘] 29714번: 브실이의 구슬 아이스크림 (Python)

 

오답 코드 (시간초과)

import sys
input=sys.stdin.readline

N=int(input().rstrip())
marbles_list=list(map(int, input().rstrip().split()))
marbles={}
for i in range(N):
    if marbles_list[i] in marbles.keys():
        marbles[marbles_list[i]]+=1
    else:
        marbles[marbles_list[i]]=1

Q=int(input().rstrip())
continue_std=True
for _ in range(Q):
    if continue_std:
        temp=marbles.copy()
    continue_std=False
    ai, *Ai=map(int, input().rstrip().split())
    bi, *Bi=map(int, input().rstrip().split())
    for i in range(ai):
        if Ai[i] in temp.keys():
            temp[Ai[i]]-=1
            if temp[Ai[i]]<0:
                continue_std=True
                break
        else:
            continue_std=True
            break
    if continue_std:
        continue

    for i in range(bi):
        if Bi[i] in temp.keys():
            temp[Bi[i]]+=1
        else:
            temp[Bi[i]]=1

    marbles=temp.copy()

print(sum(marbles.values()))
for key, value in marbles.items():
    for _ in range(value):
        print(key, end=" ")

오답 코드에서 개선해야할 부분은 아래와 같다.

기존에는 현재 가지고 있는 구슬에서 Ai의 구슬을 하나씩 빼보고, 현재 가지고 있는 구슬의 갯수가 0보다 작아지면 넘어가는 방식인데, 이 코드에는 한 가지 문제점이 있다.

좌: 오답 코드 (시간초과) 우: 정답 코드

 

Ai가 진행 조건에 맞는지 확인하기 위해 marble을 copy한 temp dict이 필요하여, 이를 만들기 위해 copy()를 반복적으로 사용한다는 것이다.

copy()는 시간 복잡도가 O(N)이고, 특정한 경우에서만 copy()하게끔 조건을 추가했음에도 시간 초과 문제가 지속되었다.

 

이를 우측과 같은 코드로 수정하여 대략, N^2에서 3N 수준의 시간 감소가 발생한 것으로 보인다.

 

시간을 많이 사용하는 함수들을 반복적으로 사용하는 것은 주의하자.