이번에는 백준 2776번 암기왕 문제를 풀어보았습니다.
수첩 2에 적힌 각 숫자가 수첩 1에 존재하는지만 확인하면 되는 문제입니다.
map을 이용해 수첩 1의 숫자들을 저장한 뒤, 수첩 2의 각 숫자를 find()로 조회하는 방식으로 해결하였습니다.
문제 설명
수첩 1에는 연종이가 하루 동안 본 숫자들이 적혀 있습니다.
수첩 2에는 동규가 질문한 숫자들이 적혀 있습니다.
수첩 2의 각 숫자에 대해
수첩 1에 존재하면 1
존재하지 않으면 0을 출력하면 됩니다.
테스트 케이스가 여러 개 주어지므로 각 테스트 케이스마다 독립적으로 확인해야 합니다.
풀이 아이디어
수첩 1의 숫자들을 map에 저장합니다.
n1[num] = 1;이후 수첩 2의 숫자를 하나씩 입력받으면서
n1.find(num)을 이용해 해당 숫자가 수첩 1에 존재하는지 확인합니다.
존재한다면 1, 존재하지 않는다면 0을 결과 벡터에 저장합니다.
마지막에 저장해둔 결과들을 입력받은 순서대로 출력합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int T,N,M;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
vector<vector<int>> ret;
for (int i=0; i<T; i++) {
map<int, int> n1;
cin >> N;
for (int j=0; j<N; j++) {
int num;
cin >> num;
n1[num] = 1;
}
ret.push_back(vector<int>());
cin >> M;
for (int j=0; j<M; j++) {
int num;
cin >> num;
if (n1.find(num) != n1.end()) ret[i].push_back(1);
else ret[i].push_back(0);
}
}
for (int i=0; i<T; i++) {
for (int j=0; j<ret[i].size(); j++) {
cout << ret[i][j] << '\n';
}
}
return 0;
}풀이 흐름
-
테스트 케이스의 개수
T를 입력받습니다. -
각 테스트 케이스마다 수첩 1의 숫자들을 저장할
map을 생성합니다. -
수첩 1의 숫자를 모두
map에 저장합니다. -
수첩 2의 숫자를 하나씩 입력받습니다.
-
현재 숫자가 수첩 1에 존재하는지
find()로 확인합니다. -
존재하면
1, 존재하지 않으면0을 결과 벡터에 저장합니다. -
모든 테스트 케이스를 처리한 후 결과를 순서대로 출력합니다.
구현 포인트
1. 수첩 1의 숫자 저장
map<int, int> n1;각 테스트 케이스마다 새로운 map을 생성합니다.
수첩 1의 숫자는
n1[num] = 1;과 같이 저장합니다.
이 문제에서는 실제 value 값은 중요하지 않고, 해당 숫자가 존재하는지만 확인하면 됩니다.
즉, map을 사실상 집합처럼 사용한 것입니다.
2. 테스트 케이스마다 map을 새로 생성
for (int i=0; i<T; i++) {
map<int, int> n1;n1이 반복문 내부에서 선언되어 있기 때문에 하나의 테스트 케이스가 끝나면 해당 map도 사라집니다.
따라서 이전 테스트 케이스의 숫자가 다음 테스트 케이스에 영향을 주지 않습니다.
3. 존재 여부 확인
if (n1.find(num) != n1.end())map::find()는 해당 key가 존재한다면 그 원소를 가리키는 iterator를 반환합니다.
존재하지 않는다면
n1.end()을 반환합니다.
따라서
n1.find(num) != n1.end()이면 현재 숫자가 수첩 1에 존재한다는 의미입니다.
4. find()를 사용하는 이유
다음과 같이 확인할 수도 있을 것처럼 보입니다.
if (n1[num])하지만 map에서 operator[]를 사용하면 해당 key가 존재하지 않는 경우에도 새로운 원소가 생성됩니다.
반면
n1.find(num)은 존재 여부만 확인하고 새로운 원소를 만들지 않습니다.
따라서 이 문제처럼 단순히 존재 여부만 검사할 때 find()를 사용하는 것이 적절합니다.
5. 수첩 2의 입력 순서 유지
문제에서는 수첩 2에 적혀 있는 순서대로 결과를 출력해야 합니다.
따라서 수첩 2 자체를 정렬하지 않고 입력되는 순서대로 바로 확인합니다.
for (int j=0; j<M; j++) {
int num;
cin >> num;현재 숫자에 대한 결과를 바로
ret[i].push_back(1);또는
ret[i].push_back(0);으로 저장하므로 원래 질문 순서가 유지됩니다.
6. 테스트 케이스별 결과 저장
vector<vector<int>> ret;전체 테스트 케이스의 결과를 저장하기 위해 2차원 벡터를 사용하였습니다.
새로운 테스트 케이스를 시작할 때마다
ret.push_back(vector<int>());로 빈 벡터를 하나 추가합니다.
이후 해당 테스트 케이스의 결과를
ret[i].push_back(...)형태로 저장합니다.
7. 결과 출력
for (int i=0; i<T; i++) {
for (int j=0; j<ret[i].size(); j++) {
cout << ret[i][j] << '\n';
}
}모든 테스트 케이스가 끝난 뒤 저장했던 결과를 순서대로 출력합니다.
수첩 2의 각 숫자마다 결과 한 개를 출력해야 하므로 매 결과마다 줄바꿈을 수행합니다.
시간복잡도
map은 내부적으로 균형 이진 탐색 트리 형태로 동작하므로 삽입과 탐색에
O(log N)의 시간이 필요합니다.
수첩 1의 N개 숫자를 삽입하는 데
O(N log N)이 필요합니다.
수첩 2의 M개 숫자를 탐색하는 데
O(M log N)이 필요합니다.
따라서 테스트 케이스 하나당 전체 시간복잡도는
O((N + M) log N)입니다.
