백준 14713번: 앵무새

 

풀이

  주어진 N개의 문장으로 마지막 문장을 만들 수 있는지 출력하면 된다. 단, 조건은 N개의 문장과 같은 순서로 단어가 나열되어야 한다. 첫 번째 단어가 가장 먼저 나타나야 하므로, 자료구조 중에서 선입선출의 특징을 갖고 있는 큐를 사용하였다. 입력 받은 문자열을 ' '을 기준으로 나눠 큐에 저장한 다음, 마지막 문장에서 큐의 순서대로 단어가 나타나는지 확인하면 된다.

 

 

  string 변수를 다루다보니 여러 라이브러리를 사용했는데, 특히 c++에서는 string 변수에 대한 split() 메소드가 없어서 직접 만들어 사용하였다.

queue<string> split(string input, char delimiter) {
	queue<string> answer;
	stringstream ss(input);
	string temp;

	while (getline(ss, temp, delimiter)) {
		answer.push(temp);
	}

	return answer;
}

 

코드

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

#define MAX 101
using namespace std;

int N;
string S, L;
queue<string> q[MAX];
queue<string> words;
bool possible = false;

void init();
queue<string> split(string str, char delimiter);

int main() {
	init();
	cin >> N;
	cin.ignore();

	for (int i = 0; i < N; i++) {
		getline(cin, S);
		q[i] = split(S, ' ');
	}

	getline(cin, L);
	words = split(L, ' ');

	while (!words.empty()) {
		possible = false;
		string word = words.front();
		for (int i = 0; i < N; i++) {
			if (!q[i].empty() && !word.compare(q[i].front())) {
				q[i].pop();
				possible = true;
				break;
			}
		}
		words.pop();

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

	for (int i = 0; i < N; i++) {
		if (!q[i].empty()) possible = false;
	}
	if (possible) cout << "Possible";
	else cout << "Impossible";

	return 0;
}

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

queue<string> split(string input, char delimiter) {
	queue<string> answer;
	stringstream ss(input);
	string temp;

	while (getline(ss, temp, delimiter)) {
		answer.push(temp);
	}

	return answer;
}