[백준(BOJ)/C++] 14713번: 앵무새 - 코딩밥상

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

14713번: 앵무새

접근 방법

 이 문제의 주안점은 앵무새의 문장마다 단어의 순서대로 결과값과 비교하여 단어들이 올 수 있는지 비교하는 것이었다.

즉 앵무새의 문장에서 단어들이 선입 선출(FIFO)로 나올 수 있다면 Possible, 없다면 Impossible인 것이다.

따라서 선입 선출을 다루기에 적합한 자료구조인 큐를 이용하였고 앵무새의 문장을 각각 따로 구분하여 넣어줄 자료구조로 벡터를 선택했다.

 

getline()함수에 대해서 간략하게 이해한바는 일반적으로 사용하던 cin과 다르게 띄어쓰기가 아닌 행바꿈을 통해 입력되어 문장 단위로 입력을 받을 수 있고, 사용 시 주의할 점은 앞서 정수를 입력 받을 때 했던 엔터가 버퍼에 남아 cin.ignore를 사용해야 한다. 이걸 빼먹으면 버퍼에 남아있던 엔터가 그대로 들어와 입력을 받은것으로 처리된다.

알고리즘

 입력받은 앵무새의 문장을 인덱스 단위로 하나하나 처리하여 띄어쓰기가 나타나면 단어로 쪼개 큐에 넣고

비교할 문장(L) 또한 문장으로 입력받고 같은 방법으로 하나하나 단어로 쪼갠다음, 큐에 들어있던 단어들과 비교하여 queue.front()에 있는 단어들과 같으면 통과, 다르면 Impossible을 출력하고 프로그램을 종료하도록 짰다.

 

빼먹으면 안되는 반례가 있는데 마지막에 큐들에 단어가 남아있는지 꼭 체크해야한다.

비교 문장(L)에 앵무새의 문장 중 빼먹은 단어가 있는 경우이다.

정답 코드

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

int main(){
    vector<queue<string>> str_vector(100);
    
    int n;
    cin>>n;
    cin.ignore();
    
    for(int i=0; i<n; i++){ //큐에 앵무새의 문장을 단어 단위로 순서대로 넣어줌
        string bird;
        getline(cin, bird);
        
        string str_push="";
        for(int j=0; j<bird.length(); j++){
            if(bird[j] == ' '){
                str_vector[i].push(str_push);
                str_push="";
            }
            else{
                str_push += bird[j];
            }
            
            if(j == bird.length()-1) str_vector[i].push(str_push);
        }
        
    }
    
    string cmp; //비교문(L) 입력 받기
    getline(cin, cmp);
    
    string cmp_word="";
    for(int i=0; i<cmp.length(); i++){  //가능한 문장인지 체크
        
        if(cmp[i] == ' ' || i == cmp.length()-1){
            if(i == cmp.length() - 1){
                cmp_word += cmp[i];
            }
            
            bool flag = false;
            
            for(int j=0; j<n; j++){
                if(cmp_word == str_vector[j].front()){
                    str_vector[j].pop();
                    flag = true;
                    break;
                }
            }
            
            if(!flag){
                cout<<"Impossible"<<'\n';
                return 0;
            }
            
            cmp_word="";
        }
        else{
            cmp_word += cmp[i];
        }
    }
    
    for(int i=0; i<n; i++){ //큐에 남은 문자가 있으면 불가능
        if(!str_vector[i].empty()){
            cout<<"Impossible"<<'\n';
            return 0;
        }
    }
    
    cout<<"Possible"<<'\n';
}