백준 1764번
오늘 풀어본 문제는 백준의 1764번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 $N$, 보도 못한 사람의 수 $M$이 주어진다. 이어서 둘째 줄부터 $N$개의 줄에 걸쳐 듣도 못한 사람의 이름과, $N+2$째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 $20$ 이하이다. $N$, $M$은 $500,000$ 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
풀이과정
첫 번째 시도
문제를 읽어보니 ‘듣도 못한 사람’인 동시에 ‘보도 못한 사람’을 찾기만 하면 되는 것 같았다. 그래서 먼저 입력받는 ‘듣도 못한 사람’ 들의 이름를 저장해두고, ‘보도 못한 사람’의 이름이 ‘듣도 못한 사람’ 중에 일치하는 이름이 있는지 확인하여 이를 저장해두는 방식으로 문제를 해결하고자 하였다.
이를 위해서 ‘듣도 못한 사람’을 저장하기 위한 자료 구조로, std::unordered_set 을 선택하였다. 요즘 unordered 시리즈가 자주 보이는 것 같다. 사용법은 std::unordered_map 과 비슷한데, 저장할 값이 따로 있는 것은 아니고 이름 자체를 키로 사용하면 될 것 같아서 std::unordered_set 을 이용하였다.
또한, ‘보도 못한 사람’의 이름이 ‘듣도 못한 사람’ 중에 일치하는 이름과 일치하는 것이 있을 때, 이 ‘듣보잡’의 이름을 저장하기 위한 자료 구조로 std::priority_queue 를 사용하였다. 자동으로 정렬를 해주기 때문에 편하다고 생각하여 사용하였다.
이번에 문제를 풀 때는 std::unordered_set 과 std::priority_queue 모두 사용방법을 숙지하고 있었기 때문에 따로 참고한 글은 없다. 사용 방법이 궁금한 사람은 구글 등에 직접 검색해보면 알 수 있을 것이다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
unordered_set<string> neverHeard;
priority_queue<string, vector<string>, greater<string>> neverHeardAndSeen;
int numberOfNeverHeard, numberOfNeverSeen;
int numberOfNeverHeardAndSeen = 0;
string tempPerson;
cin >> numberOfNeverHeard >> numberOfNeverSeen;
while (numberOfNeverHeard--) {
cin >> tempPerson;
neverHeard.insert({ tempPerson });
}
while (numberOfNeverSeen--) {
cin >> tempPerson;
if (neverHeard.count(tempPerson)) {
numberOfNeverHeardAndSeen++;
neverHeardAndSeen.push(tempPerson);
}
}
cout << numberOfNeverHeardAndSeen << "\n";
while (!neverHeardAndSeen.empty()) {
cout << neverHeardAndSeen.top() << "\n";
neverHeardAndSeen.pop();
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
생각보다 싱겁게 끝난 문제였다. STL을 사용하는 것이 꽤 편리하긴 하다. 오랜 시간에 걸쳐 머리 좋은 사람들이 뭉쳐 이리저리 굴리며 테스트를 했기 때문에 그럴 법도 하긴하다.
그래도 가끔은 이렇게 날로 먹는 날도 있어야 하지 않겠는가? 그래야 해석학 게임 프로젝트를 할 시간이 생긴다. 오늘의 날먹은 내가 PS에 대한 의지가 꺾이지 않도록 도와준 날이라 가능했다고 생각해보려 한다.
그러나 날먹이긴 했어도 나름 머리를 굴렸기 때문에 가능했다고 생각한다. 만약 PS를 요 며칠간 다시 하지 않았더라면, 무식하게 벡터를 사용해서 문제풀이를 시도하려다가 시간초과가 나서 아직도 머리를 쥐어뜯고 있을지도 모른다.
$O(1)$ 의 시간복잡도로 탐색을 수행할 수 있는 해시테이블을 처음부터 사용하려 한 것은, 어쩌면 나름대로의 노력의 성과일지도 모르는 것 아니겠는가?
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1764