정답비율: 27.840%
문제
자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다.
1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 그렇기 에 pps789는 앵무새 한 마리 대신 앵무새 N마리를 이용하여 자신의 발견을 기록하였으며, 이 앵무새들을 cseteram을 향해 날렸다.
한편 섬의 반대편에서 탐험을 계속하던 cseteram은 앵무새 N마리가 자신에게 날아와 각자 할 말을 하는 것을 보고 당황하였다. pps789가 긴 글을 전달하고 싶었던 것은 알아차렸지만, 각각의 앵무새들이 말하는 것을 차례대로 기록하다 보니 원문이 무엇인지 알 수 없을 정도로 단어의 순서가 엉켜버린 것이다. 대신 그는 관찰을 통해 몇 가지 규칙을 발견할 수 있었다.
- 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
- 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다.
- 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
- 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.
앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때 까지 단어를 받아적는다. pps789가 각각의 앵무새들에게 전달한 문장 Si와, cseteram이 받아 적은 문장 L이 주어진다. 이때 문장 L이 위 규칙들을 이용하여 나올 수 있는 문장인지 판별하시오.
입력
첫 번째 줄에 앵무새의 수 N (1 ≤ N ≤ 100) 이 주어진다.
두 번째 줄부터 N개의 줄에 걸쳐 각 앵무새가 말한 문장 Si (1 ≤ i ≤ N) 가 주어지는데, 각 문장을 이루는 단어는 스페이스 한 칸을 구분으로 하여 주어진다. 문장 Si를 이루는 단어의 수는 1개 이상 100개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성되어있다.
N + 2 번째 줄에는 cseteram이 받아 적은 문장 L이 주어진다. 문장 L을 이루는 단어의 수는 1개 이상 10000개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성된다.
출력
문장 L이 가능한 문장이라면 Possible을, 불가능한 문장이라면 Impossible을 출력한다.
예제 입력 1
1
2
3
4
5
3
i want to see you
next week
good luck
i want next good luck week to see you
예제 출력 1
1
Possible
예제 입력 2
1
2
3
4
2
i found
an interesting cave
i found an cave interesting
예제 출력 2
1
Impossible
예제 입력 3
1
2
3
4
2
please
be careful
pen pineapple apple pen
예제 출력 3
1
Impossible
문제 풀이
앵무새들은 단어들을 순서대로 말하므로 큐로 문제를 풀어보자.
각 앵무새가 말하는 문장들과 실제로 들은 문장을 큐에 저장하고 반복문으로 각 큐의 맨 앞에 있는 단어가 실제로 들은 문장이 저장되어 있는 큐의 맨 앞과 같으면 pop 시킨다.
반복문을 다 돌았는데 일치하는 단어가 없거나 실제로 들은 문장이 모두 다 pop 되었는데 앵무새들이 말해야 할 단어들이 남아있다면(앵무새들은 모든 단어들을 다 말해야 하므로) impossible을 출력하고 그렇지 않으면 possible을 출력한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from typing import List
from collections import deque
# 앵무새의 수 n 입력받기
n = int(input())
parrot = []
# 앵무새가 말한 문장 입력받아서 큐로 저장
for _ in range(n):
parrot.append(deque(input().split()))
def possible(sentence: List[str], parrot: List[deque]) -> bool :
i = 0
cnt = 0
# sentence가 빌 때까지 반복해서 실제 문장의 단어가 있는지 확인
while sentence:
if parrot[i] and sentence[0] == parrot[i][0]:
parrot[i].popleft()
sentence.popleft()
cnt = 0
else:
if cnt == n: # 실제 문장의 단어가 세 앵무새의 큐에 없을 때
return False
cnt += 1
i = (i + 1) % n # i = 0, 1, 2
# while 문이 끝났다는 건 sentence가 다 pop돼서 비었다는 뜻
# 앵무새가 모든 단어들을 다 말해야 하므로 각 앵무새의 큐가 비어있는지 확인
empty = 0
for j in range(n):
if not parrot[j]:
empty += 1
if empty == n:
return True
else:
return False
# 실제 문장 입력받기
sentence = deque(input().split())
if possible(sentence, parrot):
print("Possible")
else:
print("Impossible")