[S2] 백준 14713번 앵무새 C++ 해시맵, 문자열

리뷰

 

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

문제가 잘 이해되지 않았는데 예상되는 케이스를 반례로 넣었더니 AC를 받았다.

알고리즘 분류에 큐가 적혀있는데 큐 없이도 문제가 해결 가능했다, 어쩌면 더 최적화 코드가 있을 지도?

 

 

전역 변수

• n : 앵무새의 개수
• idx : 각 앵무새가 읽은 단어의 인덱스를 저장하기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. key가 문자열, value가 pair<int, int>타입인 해시맵 dic을 초기화 해준다.
2. n값을 입력 받고, 이후 문자열을 getline으로 받을 것이기 때문에 cin.get()를 수행해 준다.
3. n번의 반복문을 실행하고, 정수형 변수 index를 0으로 초기화 해준다.
4. 빈 문자열 변수 s를 초기화 하고 getline을 통해 cin값을 s에 저장해 준다.
5. stringstream 타입의 변수 ss에 문자열 s를 대입해 준다.
6. getline을 통해 ss에서 공백을 구분으로 문자열 s에 문자열을 파싱해 준다.
7. 파싱된 값을 해시맵의 키로 설정하고 값을 현재 앵무새의 인덱스 i와, 단어의 인덱스 index를 후위 증가시켜 넣는다.
8. 모든 앵무새의 단어를 받고 난 후 이제 받아쓴 단어와 비교를 해 줄 차례다.
9. 빈 문자열 변수 s를 초기화 하고, getline을 통해 해당 문자열에 한줄을 입력 받는다.
10. 동일하게 stringstream 타입의 변수 ss에 문자열 s를 대입해 준다.
11. geline을 통해 ss에서 공백을 구분으로 문자열 s에 문자열을 파싱해 준다.
12. 만약 dic의 s키가 없다면, 존재하지 않는 단어를 적은 것이므로 Impossible을 출력하고 탐색을 종료한다.
13. dic의 s키가 존재한다면, pair<int, int> 타입의 변수 d에 해당 큐의 첫번 째 값을 뽑아준다.
14. d의 second가 idx의 d.first와 같은지 비교해 준다. 아니라면 단어의 순서가 변경되 것이므로 Impossible
15. 같다면 idx의 d.first(앵무새)의 값을 증가시켜 준 뒤 dic에서 s를 제거해 준다.
16. 모든 탐색이 종료될 때 까지 Impossible이 출력되지 않았다면 한 가지 로직을 더 수행해 준다.
17. dic의 size가 1이상 이라면 모든 앵무새의 말을 받아 적지 못한 것이므로 Impossible을 출력한다.
18. dic의 size가 0이라면 모든 앵무새의 말을 받아 적은 것이기에 Possible을 출력한다.

 

참고 사항

• 앵무새가 말한 내용을 한 줄로 받아야 하기 때문에 stringstream과 getline을 사용해 주었다.
• 각 단어를 말한 앵무새와 몇번째로 말했는지를 저장하기 위해 dic의 값으로 pair<int, int> 를 사용했다.
• 앵무새 존재 여부는 앵무새를 1-based-index를 통해 0일 경우 없다고 판단하였다.
• idx 배열은 각 앵무새가 몇번째 단어를 말할 차례인지를 확인 하기 위한 배열이다.

 

정답 코드

#include<iostream>
#include<sstream>
#include<unordered_map>
#include<string>
#define pii pair<int, int>
using namespace std;
int n;
int idx[101];
string s;
unordered_map<string, pii> dic;

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

	cin >> n; cin.get();
	for (int i = 1; i <= n; ++i) {
		int index = 0;
		getline(cin, s);
		stringstream ss(s);
		while (getline(ss, s, ' ')) dic[s] = { i, index++ };
	}

	getline(cin, s);
	stringstream ss(s);
	while (getline(ss, s, ' ')) {
		if (!dic[s].first || dic[s].second != idx[dic[s].first]) {
			cout << "Impossible";
			return 0;
		}
		else {
			idx[dic[s].first]++;
			dic.erase(s);
		}
	}

	if (!dic.size()) cout << "Possible";
	else cout << "Impossible";
}