[BOJ/백준 14713][C++] 앵무새

문제

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

백준 14713

백준 14713

 

문제 내용

앵무새들의 말로 문장 L을 만들 수 있는지 없는지 판단하는 문제이다.

 

문제 풀이

앵무새가 말하는 데에는 규칙이 있다.

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

위 규칙을 살펴보면, 1번과 2번 규칙을 통해서 문제 해결에 queue를 사용해야 함을 알 수 있다.

자신의 문장에서는 순서가 바뀌면 안 되기 때문에 무조건 앞에 있는 단어부터 사용해야 한다.

또한 4번 문장에서 단어의 중복이 없다고 했으므로, 문장 L과 일치하는 단어를 찾을 때 여러 가지가 매칭 될 확률은 없다.

 

자세한 풀이는 코드를 읽으면 이해될 것이다.

코드 아래에 풀이를 적어뒀다.

 

코드

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


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

	//입력
	int n; cin >> n;
	vector<queue<string>>q(n+1); //마지막은 기준 문자열
	string tmp;
	getline(cin, tmp); //위에서 cin으로 정수 입력받고 남은 개행문자 처리
	for (int i = 0; i < n+1; i++) {
		getline(cin, tmp);
		istringstream ss(tmp);
		string stringBuffer;
		while (getline(ss, stringBuffer, ' ')) { //공백으로 구분하여 넣음
			q[i].push(stringBuffer);
		}
	}

	bool check = false;
	//문제 해결
	int queue_size = q[n].size();
	for (int i = 0; i < queue_size; i++) {
		string base_word = q[n].front();
		for (int j = 0; j < n; j++) {
			if (!q[j].empty() && q[j].front() == base_word) {
				q[j].pop();
				q[n].pop();
				check = true;
				break;
			}
		}
		if (check == false) {
			cout << "Impossible\n";
			return 0;
		}
		else {
			check = false;
		}
	}

	//결과 출력
	//마지막에 단어가 남을 수도 있다.
	//이거 체크 안하면 틀림
	for (int i = 0; i < n; i++) {
		if (!q[i].empty()) {
			cout << "Impossible\n";
			return 0;
		}
	}
	
	cout << "Possible\n";
}

 

문제 코드 설명

1) 입력

cin으로 정수를 입력받으면 정수 뒤에 붙어있는 개행 문자(\n) 이전까지 읽어가게 된다.

따라서 우리가 원하는 문장을 입력받기 전에 getline()으로 개행 문자를 처리해주어야 한다.

이후 문장별로 문자열을 입력받아, 공백을 기준으로 단어를 나누고, 이를 queue에 집어넣는 과정이 필요하다.

공백으로 단어를 나누고 queue에 집어넣는 과정에서 istringstream을 사용했다.

 

2) 문제 해결

이제 반복문을 돌면서 문장 L을 어떻게 만들 수 있는지를 확인하면 된다.

queue배열을 돌면서 각각의 front 값이 무엇인지 확인하고, 일치하는 것이 있으면 pop() 해주면 된다.

만약, queue배열의 모든 front 값이 문장 L의 front와 같은 것이 없다면, 바로 Impossible이라고 출력하고 끝내면 된다.

 

3) 결과 출력

마지막에 앵무새가 말한 단어들(문장 L이 아닌 단어들)이 남아있는지 확인하는 과정이 필요하다.

모든 단어를 사용했다면 Possible을 출력하면 된다.