앵무새 //14713

• 문제
  자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다.
  1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 그렇기 에 pps789는 앵무새 한 마리 대신 앵무새 N마리를 이용하여 자신의 발견을 기록하였으며, 이 앵무새들을 cseteram을 향해 날렸다.
  한편 섬의 반대편에서 탐험을 계속하던 cseteram은 앵무새 N마리가 자신에게 날아와 각자 할 말을 하는 것을 보고 당황하였다. pps789가 긴 글을 전달하고 싶었던 것은 알아차렸지만, 각각의 앵무새들이 말하는 것을 차례대로 기록하다 보니 원문이 무엇인지 알 수 없을 정도로 단어의 순서가 엉켜버린 것이다. 대신 그는 관찰을 통해 몇 가지 규칙을 발견할 수 있었다.

1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다.
3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.
   
   앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때 까지 단어를 받아적는다. pps789가 각각의 앵무새들에게 전달한 문장 Si와, cseteram이 받아 적은 문장 L이 주어진다. 이때 문장 L이 위 규칙들을 이용하여 나올 수 있는 문장인지 판별하시오.
   
   //시간 제한: 1초, 메모리 제한: 512MB

-입력
첫 번째 줄에 앵무새의 수 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을 출력한다.

// Created by dongwan-kim on 2022/07/24.
#include<iostream>
#include<queue>

using namespace std;

int n, cnt;
string s, temp;
queue<string> q[100];
queue<string> ans;

int main() {
    bool possible = true;
    cin >> n;
    cin.ignore();
    for (int i = 0; i < n; i++) {	//앵무새 문장 push
        getline(cin, s);
        for (int j = 0; j < s.length(); j++) {
            if (s[j] != ' ')
                temp += s[j];
            else {
                q[i].push(temp);
                temp = "";
            }
        }
        q[i].push(temp);
        temp = "";
    }

    getline(cin, s);		//cseteram이 받아 적은 문장 ans에 push
    for (int j = 0; j < s.length(); j++) {
        if (s[j] != ' ')
            temp += s[j];
        else {
            ans.push(temp);
            temp = "";
        }
    }
    ans.push(temp);

    while (!ans.empty()) {		//문장 가능한지 확인하는 반복문
        for (int i = 0; i < n; i++) {
            if (!q[i].empty() && q[i].front() == ans.front()) {
                q[i].pop();
                ans.pop();
                cnt = 0;
            } else {
                cnt++;
                if (cnt == n) {
                    possible = false;
                    break;
                }
            }
        }
        if (!possible)
            break;
    }

    for (int i = 0; i < n; i++)		//모든 앵무새가 말하고 돌아갔는지 확인하는 반복문
        if (!q[i].empty())
            possible = false;


    if (possible)
        cout << "Possible";
    else
        cout << "Impossible";
}

풀이

처음 문제를 보자마자 queue 배열을 만들어서 풀어야겠다고 생각했다.
queue배열을 만들어 문장을 단어로 잘라서 push해주었고,
csetertam이 받아 적은 문장을 ans큐에 push해주었다.

큐 배열들의 front와 ans의 front가 같으면 각각 pop해준 후 cnt를 0으로 초기화 해주었고, 다를 경우에는 cnt++을 하고 만약 cnt가 앵무새 숫자와 같다면,즉 ans의 문장을 완성할 수 없을 때 바로 break해주는 식으로
ans가 empty일 때까지 반복해 주었다.

ans에 담긴 문장이 다 완성되었더라도 앵무새가 다 말하고 돌아가지 않았다면 실패이므로 한번 더 반복문을 돌며 앵무새가 다 돌아갔는지 확인한 후 결과를 출력해주었다.