[BOJ/C++] 14713 앵무새(큐)

 

앵무새 여러 마리가 한 문장씩 말하는데 이때 단어를 순서대로 조합해서 마지막에 입력된 문장을 만들 수 있는지 판별하는 문제

순서와 단어의 유무를 고려해야한다!! 또한 앵무새가 말한 단어가 모두 쓰였는지도 고려해야한다.

먼저 말한 단어 순서대로 조합해야하므로 FIFO(first in first out)인 queue를 사용하여 문제를 풀 수 있다.

 

k.back() → k의 가장 뒤 원소를 가리킴

k.front() → k의 가장 앞 원소를 가리킴

k.pop() → k의 가장 앞 원소를 삭제

k.size() → 큐 사이즈 반환

k.empty() → 비었는지 bool 값 반환

k.emplace(3) → push와 같은 역할

k.swap(k_1) →k_1과 k의 원소 바꾸기

 

 

#include<iostream>
#include <string>
#include <sstream> 
#include<vector>
#include<queue>
using namespace std;

int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    int n;
    cin >> n;
    cin.ignore(); 

    vector<queue<string>> p(n);
    queue<string> s;
    string ss, word;

    // 각 앵무새가 하는 말 저장
    for(int i=0; i<n; i++){
        getline(cin, ss);
        stringstream stream(ss);
        while(stream >> word){
            p[i].push(word); 
        }
    }

    getline(cin, ss);
    stringstream stream(ss);
    while(stream >> word){
        s.push(word);
    }

    while(!s.empty()){
        bool isPop = false;

        for(int i=0; i<n; i++){ 
            //cout << s.front() << p[i].front() <<"\n";
            if(!p[i].empty() && p[i].front() == s.front()){
                p[i].pop();
                s.pop();
                isPop = true; 
                break;
            }
        }
        if (!isPop) {
            cout << "Impossible";
            return 0;
        }

    }

    for (int i = 0; i < n; i++) {
        if (!p[i].empty()) {
            cout << "Impossible";
            return 0;
        }
    }

    cout << "Possible";


}