https://www.acmicpc.net/problem/10816
문제 해결 과정
착안
(최초 접근 방법) STL의 <unordered_map> 헤더에 포함된 std::unordered_map<> 클래스를 활용하여 입력되는 숫자를 키, 반복되는 개수를 값으로 가지도록 구현하고자 하였다(기본 오버로딩 되어있는 [] 연산자 활용).
(다른 접근 방법) 이전에 다른 문제들을 풀어보는 동안 숫자형 키 값을 사용할 때 std::unordered_map<> 클래스를 사용하는 것이 다소 비효율적인 결과를 보였었던 경험이 있었다. 따라서 해당 문제의 알고리즘 분류를 참고하여 아래와 같은 풀이 방법을 생각해보았다.
- 입력받는 카드의 번호를 전부 배열에 저장한다.
- 입력이 완료되면 해당 배열을 정렬한다.
- 이진 탐색(binary search, 이분 탐색)을 통해 찾고자 하는 카드가 처음 또는 마지막으로 등장하는 index를 구한다.
- 두 수의 차를 이용해 문제에서 요구하는 답을 구한다.
이진 탐색을 수행하는 함수의 구현을 응용하면 카드가 처음으로 등장하는 index와 마지막으로 등장하는 index + 1의 값을 구할 수 있으므로(아래 코드 참고), 이를 활용하여 문제를 해결하고자 하였다.
구현
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int Cards[500000];
int SearchLeft(int num)
{
int left = 0, right = N;
while (left < right)
{
int middle = (left + right) / 2;
if (num > Cards[middle])
left = middle + 1;
else
right = middle;
}
return right;
}
int SearchRight(int num)
{
int left = 0, right = N;
while (left < right)
{
int middle = (left + right) / 2;
if (num < Cards[middle])
right = middle;
else
left = middle + 1;
}
return left;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++)
cin >> Cards[i];
sort(&Cards[0], &Cards[N - 1] + 1);
int M;
cin >> M;
while (M--)
{
int card;
cin >> card;
cout << SearchRight(card) - SearchLeft(card) << " ";
}
cout << "\n";
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 10814번: 나이순 정렬 (0) | 2023.06.25 |
---|---|
[Baekjoon] 1021번: 회전하는 큐 (0) | 2023.06.25 |
[Baekjoon] 2331번: 반복수열 (0) | 2023.06.22 |
[Baekjoon] 1931번: 회의실 배정 (0) | 2023.06.21 |
[Baekjoon] 10844번: 쉬운 계단 수 (0) | 2023.06.20 |
댓글