https://www.acmicpc.net/problem/1920
문제 해결 과정
착안
반복적으로 탐색을 빠르게 수행하는 것이 문제에서 요구하는 핵심이므로, 아래와 같이 일반적으로 탐색 속도가 매우 빠른 것으로 알려져 있는 방법으로 각각 문제를 해결하고자 하였다.
- 해시(hash) 맵을 사용한 방법
- 이진 탐색(binary search, 이분 탐색)을 사용하는 방법
구현
[스포 주의] (해시 맵 사용) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
// 해시 맵 사용
#include <iostream>
#include <unordered_set>
using namespace std;
unordered_set<int> Numbers;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
while (N--)
{
int num;
cin >> num;
Numbers.emplace(num);
}
cin >> N;
while(N--)
{
int num;
cin >> num;
auto iter = Numbers.find(num);
cout << (iter != Numbers.end() ? "1" : "0") << "\n";
}
return 0;
}
[스포 주의] (이진 탐색 사용) 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
// 이진 탐색 사용
#include <iostream>
#include <algorithm>
using namespace std;
int Numbers[100000];
void BinarySearch(int num, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (num == Numbers[middle])
{
cout << "1\n";
return;
}
if (num < Numbers[middle])
right = middle - 1;
else
left = middle + 1;
}
cout << "0\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> Numbers[i];
sort(&Numbers[0], &Numbers[N]);
int M;
cin >> M;
while (M--)
{
int num;
cin >> num;
BinarySearch(num, 0, N - 1);
}
return 0;
}
실행 결과
해시 맵의 경우에는 문자열 데이터를 다룰 때에 더 효과적인 것 같다.
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 11650번: 좌표 정렬하기 (0) | 2023.06.11 |
---|---|
[Baekjoon] 2579번: 계단 오르기 (0) | 2023.06.09 |
[Baekjoon] 7785번: 회사에 있는 사람 (0) | 2023.06.07 |
[Baekjoon] 1932번: 정수 삼각형 (0) | 2023.06.05 |
[Baekjoon] 1018번: 체스판 다시 칠하기 (0) | 2023.06.04 |
댓글