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

[문제]

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

N마리의 앵무새들의 말을 조합하여 문장 L을 만들 수 있는지 판단하는 문제이다. 앵무새는 아래와 같은 규칙을 가지고 말한다.

1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 앵무새는 이 단어들을 순서대로 말한다.
3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.

[사용 알고리즘]

큐

[풀이 핵심]

• 문장을 입력받을 때 공백을 포함해서 입력받아야하므로 string 헤더파일의 getline() 함수를 사용한다.
• 아래 순서와 같이 풀면 해결할 수 있다.

  1. 앵무새가 말하는 문장을 단어로 쪼개서 queue에 저장하고 문장 L도 단어로 쪼개서 queue에 저장한다.
  2. 문장L의 단어 개수만큼 for문을 돌면서 각 앵무새의 첫 단어(queue의 front)와 문장 L의 첫 단어를 비교해서 같은 경우 해당 단어를 외우고 있는 앵무새의 queue와 문장 L의 queue를 pop해준다. 만약 모든 앵무새의 첫단어가 문장 L의 첫 단어와 다를 경우 문장을 만들 수 없는 것이므로 "Impossible" 을 출력한다.
  3. for문이 끝난 후 아직 pop되지 않은 앵무새의 단어가 존재할 경우 문장 L을 만들고 앵무새가 말한 단어가 남아 있다는 뜻으로 최종문장이 L+alpha라는 뜻이다. 따라서 만드려는 문장 L이 아니므로 "Impossible"을 출력한다.
  4. 나머지 경우에는 "Possible"을 출력한다.

[코드]

//boj14713번_앵무새_큐

#include<iostream>
#include<vector>
#include<queue>
#include<string>

using namespace std;

int main() {
	int N;
	cin >> N;

	cin.ignore();

	vector<queue<string>> bird;

	for (int i = 0; i < N; i++) {
		string str;
		getline(cin, str);

		string word = "";

		queue<string> q;

		for (int j = 0; j < str.size(); j++) {
			if (str[j] == ' ') {
				q.push(word);
				word = "";
			}
			else {
				word += str[j];
			}
		}
		q.push(word);

		bird.push_back(q);
	}

	string L;
	getline(cin, L);

	string temp = "";

	queue<string> L_q;

	for (int i = 0; i < L.size(); i++) {
		if (L[i] == ' ') {
			L_q.push(temp);
			temp = "";
		}
		else {
			temp += L[i];
		}
	}
	L_q.push(temp);

	int size = L_q.size();

	for (int i = 0; i < size; i++) {
		bool check = false;

		for (int j = 0; j < N; j++) {
			if (!bird[j].empty() && L_q.front() == bird[j].front()) {
				bird[j].pop();
				L_q.pop();
				check = true;
				break;
			}
		}

		if (!check) {
			cout << "Impossible";
			return 0;
		}
	}


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

	cout << "Possible";


	return 0;
}