[백준-파이썬] 21776: 가희와 읽기 쓰기 놀이

와아아~~~

이 문제를 풀어서 편안하게 잠잘 수 있겠다 ㅎㅎ
처음에는 메모리 초과 해결하느라고,
나중에는 게임 종료 후 빈 문자열이면 EMPTY 출력하는 걸 깜박해서 많이 틀렸다..

문제 보러 가기

아이디어

카드의 갯수, 사람의 수가 최대 9..!!
사람들이 어떤 순서로 카드를 낼 수 있는지를 순열로 구했다.
각 순열대로 했을 때의 결과를 리스트로 저장했고, 사전순으로 출력이니까 정렬을 한 후에 출력했다.
같은 결과가 나오면 하나로 출력하라고 해서, set을 이용했다. (set에 저장한 후에 마지막에 리스트로 바꿔서 정렬했다.)

처음에는 모든 경우의 순열을 다 구했다. 그랬더니 메모리 초과가 나왔다..!!  -예) 1번 사람이 카드 한 장, 2번 사람이 카드 한 장을 가진 경우라고 생각해보자. 사람들이 어떤 순서로 카드 낼 수 있는지 (불가능한 경우까지) 모든 경우를 다 구했을 때는 4가지이다. (1번->1번, 1번->2번, 2번->1번, 2번->2번)

그 후에는 순열을 구하는데, 각 사람이 가지고 있는 카드 수보다 더 많이 차례가 돌아오지 않게 했다~ 즉 가능한 경우만 구했다는 이야기이다. 위의 예시에서 가능한 경우만 구하면 2가지이다. (1번 -> 2번, 2번->1번)

코드

import copy
import sys

input = sys.stdin.readline

def repetition_permutation(depth):
    if depth == C:
        orders.append(tuple(copy.copy(t)))
        return

    for i in range(N):
        if people_cards_cnt[i] > t[:depth].count(i): # 그 사람이 갖고 있는 카드 수보다 더 많이 X
            t[depth] = i
            repetition_permutation(depth + 1)

MIIS = lambda: map(int, input().split())
N, C = MIIS()

people_cards_cnt = []
# 카드 패(*번 사람이 가진 카드 패- 순서대로 내야 함)
people_cards = []
for _ in range(N):
    cards = tuple(MIIS())

    people_cards.append(cards[1:])
    people_cards_cnt.append(cards[0])

# 카드 명령 내용
card_order = dict()
for i in range(1, C + 1):
    tmp = input().strip().split(',')
    card_order[i] = tmp

# 그 결과
results = set()

# 어떤 순서로 진행하는지
orders = list()
t = [-1] * C
repetition_permutation(0)


# 위 순서로 진행해보기(안 되면 중간에 X)
for i in range(len(orders)):
    now_order = orders[i]
    now_str = []
    now_idx = [0]*N
    flag = True

    for order in now_order:  # 카드 하나씩 실행해보기

        now_commands = card_order[people_cards[order][now_idx[order]]]
        now_idx[order] += 1
        for com in now_commands:  # 카드 속 명령 모두 실행
            command, key = com.split()
            if flag == False:
                break

            if command == 'ADD':
                now_str.append(key)
            elif command == 'DEL':
                # 불가능하면 에러 처리
                if len(now_str) > int(key):
                    now_str.pop(int(key))
                else:
                    results.add('ERROR')
                    flag = False
                    break

    if flag == True: # 게임 끝까지 잘 마무리하고 종료된 건지 체크
        # 게임이 끝났을 때 빈 문자열이면 EMPTY
        if not now_str:
            results.add('EMPTY')
        # 그게 아니라면
        else:
            results.add(''.join(now_str))




results = sorted(list(results))
for result in results:
    print(result)