- 문제 (14713번) : 앵무새
- 이 문제는 cseteram이 적은 문장이 N마리의 앵무새가 기억하고 있는 단어들로 만들 수 있는지 확인하는 문제
< 이 문제에서 주어지는 규칙 >
- 한 앵무새는 한 문장을 기억하고 있다. (단어의 순서 중요)
- 한 앵무새가 단어를 말하고 그 단어를 말하기 전에 다른 앵무새가 끼어들 수 있다.
- 한 앵무새가 단어를 말하는 도중에는 끼어들 수 없다.
- 어떤 단어도 2번 이상 등장하지 않는다.
- 입력 및 출력
[ 입력 ]
- 첫번째 줄에 앵무새의 수 N 입력
- 두번째줄부터 N+1번째 줄까지 N마리의 앵무새가 외우고 있는 문장 입력
- 마지막 줄에는 cseteram이 적은 문장 L이 주어짐.
앵무새가 외우고 있는 문장 : 1 ≤ 단어 ≤ 100
cseteram이 적은 문장 : 1 ≤ 단어 ≤ 10,000
각 단어는 1 ≤ 글자의 개수 ≤ 32 개의 영어소문자로 이루어져있음.
[ 출력 ]
- cseteram 이 적은 문장 L이 앵무새들의 단어로 만들어질 수 있으면 "Possible"을, 그렇지 않으면 "Impossible" 을 출력
- 문제 풀이
-
각 앵무새들이 외우고 있는 문장을 각각의 queue에 저장하고, cesteram이 입력한 문장의 가장 앞 단어와 각각의 앵무새들이 외우고 있는 단어를 비교해 문제 해결
- 앵무새들이 외우고 있는 단어는 모두 사용해야하고, 하나의 앵무새가 외우고 있는 단어의 순서는 섞이면 안됨에 주의!
-
입력에 공백이 있으므로 공백을 기준으로 자른 단어를 queue에 저장하기 위해 istringstream 을 사용.
-
또한 앵무새의 수 + 1 개만큼 queue를 사용하기 때문에 이렇게 만든 queue를 vector로 관리
-
앵무새가 외우고 있는 순서가 섞이면 안되므로 각각의 앵무새들이 외우고 있는 문장의 가장 앞 단어와 비교.
- 모든 앵무새에게 단어가 없다면 "Impossible"
- 어떠한 앵무새 queue의 front원소에 단어가 있다면 L의 단어와 front원소를 pop하며 L의 끝까지 탐색
- 최종 코드
