[파이썬/python] 백준 - 14713 앵무새

문제

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

---

문제 설명

1. N마리의 앵무새가 존재한다.
2. pps789는 cseteram에게 앵무새를 이용하여 메세지를 전달한다.
   1.  말하는 문장을 앵무새 N마리가 나누어서 기억한다.
   2. 모든 앵무새가 기억하는 단어를 전부 사용하여 메세지를 완성해야 한다.
3. 앵무새들이 전달한 메세지를 전부 사용하여 문장 L을 만들 수 있는 지 검증한다.
4. 전부 사용하는 이유
   pps789가 보낸 메세지를 앵무새들이 나눠서 전달하는 것이기 때문에 모든 단어를 사용하여 문장을 만들어야 한다.
   따라서 문장을 완성했더라도 앵무새에게 단어가 남아있으면 Impossible을 출력한다.

 

---

풀이

Queue를 사용해도 상관없지만, 함수를 reverse해서 Stack을 사용했다.

최초에는 문장을 완성했을 때 사용하지 않은 단어가 있더라도 Possible을 출력하도록 했지만, 그게 아니었다.

앵무새들이 전달 받은 단어들을 전부 사용해야 pps789가 전달한 메세지가 완성된다고 이해를 해야 한다.

따라서 문장을 완성한 후 앵무새들에게 단어가 남아있는지 한 번더 검사하여 결과를 출력했다.

1. 딕셔너리에 현재 앵무새들이 말할 수 있는 단어를 Key, Value 형태 [word, index]로 저장한다.
2. 문장 L의 단어를 pop한 후 해당 단어가 딕셔너리에 존재한다면 index 위치의 앵무새의 현재 단어를 pop한다.
   1. 딕셔너리의 문장 L의 다음 단어가 없다면 Impossible을 출력한 후 종료한다.
3. index 위치의 앵무새의 다음 단어를 딕셔너리에 저장한다.
   1. 이 때 앵무새가 모든 단어를 사용했다면 딕셔너리에 저장하지 않는다.
4. 2-3 과정을 반복하여 L 문장을 만들 수 있는지 검증한다.
5. 결과 출력 전 앵무새들에게 단어가 남아있는지 확인한다.
   1. 단어가 남아있다면 Impossible을 출력한 후 종료한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
dic = dict()
words = [list(reversed(input().strip().split())) for _ in range(n)]

for i in range(n):
    dic[words[i][-1]] = i
stack = list(reversed(input().strip().split()))

while stack:
    s1 = stack.pop()
    if s1 not in dic:
        print("Impossible")
        exit()
    idx = dic[s1]
    dic.pop(s1)
    words[idx].pop()
    if words[idx]:
        dic[words[idx][-1]] = idx

for word in words:
    if word:
        print("Impossible")
        exit()
print("Possible")

---

시간복잡도

• 앵무새(N)는 최대 100마리, 앵무새 별 가질 수 있는 단어의 수는 최대 100개이다.
• 최악의 경우 100마리의 앵무새가 100개의 단어를 전부 사용할 경우이다.
• 따라서 최대 단어의 개수인 100*100 즉, 약 $O(100*100) = O(10^4)$의 시간복잡도가 소요된다.