[파이썬/python] 백준 - 21775 가희와 자원 놀이

문제

https://www.acmicpc.net/problem/21775

---

문제 설명

1.   자원 놀이 게임을 진행한다.
   1. 자원 놀이에는 3가지의 연산 카드가 존재한다.
      1. next
         : 아무 일도 일어나지 않고 이 카드를 버린다.
      2. acquire n
         : 자연수 n이 적혀진 자원 카드를 획득하려고 시도한다.
         : 만약 자연수 n이 적혀진 자원 카드가  공용 공간에 있다면, 자신의 공간으로 가져온 후 acquire n 카드를 버린다.
         : 만약 자연수 n이 적혀진 자원 카드가 누군가의 공간에 있다면, 이 카드를 버리지 않고 돌아오는 자신의 다음 차례에 재사용한다.
      3. release n
         : 자연수 n을 공용 공간에 반납하고 이 카드를 버린다. (카드를 버릴 수 없는 경우는 주어지지 않는다.)
2. 아래 순서로 게임이 진행된다.
   1. 처음에 모든 자원 카드, 연산 카드들은 공용 공간에 놓여져 있다.
   2. 각 턴을 수행하는 사람은 1명이다.
   3.  자신의 턴이 돌아오면 다음의 행동을 수행한다.
      1. 연산 카드를 들고 있지 않은 경우
         : 더미의 맨 위에 있는 연산 카드를 뽑고, 해당 카드에 있는 연산을 즉시 수행한다.
      2. 연산 카드를 들고 있는 경우
         : 들고 있는 연산 카드에 있는 연산을 즉시 수행한다.
3. 매 턴 게임이 진행될 때 각 턴에 수행된 연산 카드의 id를 출력한다. 

 

---

풀이

이 문제의 핵심은 카드를 버리게 되는 상황과 카드를 뽑게 되는 상황이다.

만약 현재 턴의 사용자가 acquire 카드를 들고 있다면, 현재 들고 있는 카드를 사용하고, 버려야 하기 때문에 카드를 뽑지 않는다.

처음에 이 부분이 굉장히 헷갈렸다. 따라서 이 문제에서는 현재의 턴과 현재 사용하는 카드를 따로 구분해야 했다.

이 부분을 해결하면 쉽게 문제가 풀릴 것이라 생각한다.

1. 매 턴을 진행할 때 필요한 상황들은 메서드로 생성했다.
   1. user_init() : 사용자가 현재 패에 있는 acquire를 사용한다면, 손을 비운다.
   2. acquire() : 사용자가 연산 카드를 사용한다.
      1. 연산 카드의 숫자가 공용 공간에 없다면, 사용자의 공간으로 카드를 이동시킨다.
      2. 연산 카드의 숫자가 공용 공간에 존재한다면, 해당 카드를 사용한 카드를 확인하는 딕셔너리에 저장한다.
   3. release() : 사용자가 연산 카드의 숫자를 손에서 공용 공간으로 이동시킨다.
      1. use 딕셔너리에서 해당 숫자를 제거한다.
2. 매 턴이 진행할 때 마다 필요한 메서드를 사용하여 턴을 진행한 후 사용한 카드의 번호를 출력한다.

---

코드

import sys
input = sys.stdin.readline

N,T = map(int,input().split())

turns = list(map(int,input().split()))
use = {}
users = [['','',''] for _ in range(N+1)]

i = 0
def user_init(user):
    users[user] = ['','','']

def acquire(user,id, command, card_number,flag):
    if card_number in use:
        users[user] = [id,command,card_number]
    else:
        use[card_number] = user
        if flag:
            user_init(user)
    print(id)

def release(id,card_number):
    use.pop(card_number)
    print(id)

cards = [list(input().split()) for _ in range(T)]

i = 0
turn = 0
for turn in range(T):
    user = turns[turn]
    if users[user][0] != '':
        acquire(user, users[user][0],users[user][1],users[user][2],1)
    else:
        card = cards[i]
        if card[1] == 'next':
            print(card[0])
        elif card[1] == 'acquire':
            acquire(user,card[0],card[1],card[2],0)
        else:
            release(card[0],card[2])
        i += 1

---

시간복잡도

• 턴 수는 최대 $T = 5*10^5$이다.
• 매 턴마다 1개의 연산을 수행하기 때문에 약 $O(T) = O( 5*10^5)$의 시간복잡도가 소요된다.