알고리즘
백준 10815번 - 숫자 카드(C++/정렬/Merge Sort/이분 탐색)
밧지성
2024. 2. 23. 14:41
728x90
반응형
문제
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
접근법
입력이 카드개수는 500,000개, 탐색할 수도 500,000 개 이니까 그냥 for문을 통해 비교하며 탐색하면 무조건 시간 초과가 난다.
그럼 이진탐색을 해야하는데 이진탐색을 위해서는 수가 정렬되어 있어야 한다.
algorithm에서 제공해주는 std::sort 함수를 쓰면 O(nlongn)으로 정렬될 것이고, unordered_map을 사용하면 메모리를 좀 내주는 대신에 O(1)로 되겠지만, 공부개념으로 오랜만에 병합정렬을 구현해서 풀기로 했다.
병합정렬은 분할 정복 개념이 들어간다
- 분할(Divide) - 문제를 단순하게 분할
- 정복(Conquer) - 분할된 문제를 해결
- 결합(Combine) - 결과를 취합해 마무리
[3][5][1][9][2][6][4][8]을 [3][5][1][9] | [2][6][4][8]로 나눠서 정렬한다. 이 또한
[3][5] | [1][9] | [2][6] | [4][8] ,
[3] | [5] | [1] | [9] | [2] | [6] | [4] | [8]
처럼 계속 나눈다. 결합은 자기 옆의 숫자와 비교해 다시 결합한다. [3][5] | [1][9] | [2][6] | [4][8] #숫자를 적을땐 막 썻는데 이미 되어있네...?
[1][3][5][9] | [2][4][6][8]
[1][2][3][4][5][6][8][9]
가 최종 결과값이다.
시간복잡도는 O(NlogN)으로 빠른편이다.
이진 탐색은 정렬이 된 배열등에서 데이터를 탐색하는 방법이다. 중간에 있는 데이터를 기준으로 up/down을 책정하고, true인 부분을 또한 같은방법으로 비교하는 방법이다. 일반적인 탐색은 O(n) 이지만, 이진탐색은 O(logn)이 나온다.
약 97%에서 오류가 나면
3
-3 -2 -1
2
0 1
case를 한번 넣어보자
output이 0 0떠야한다. 나같은 경우는 FindNumber함수에서 int right = ownCards.size()라고 해서 범위초가가 났었다.
코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> ownCards;
vector<int> Find;
void MergeResult(int left, int mid, int right)
{
vector<int> tmpVec;
int leftIdx = left;
int rightIdx = mid+1;
while (leftIdx <= mid && rightIdx <= right)
{
if (ownCards[leftIdx] <= ownCards[rightIdx])
{
tmpVec.push_back(ownCards[leftIdx]);
leftIdx++;
}
else
{
tmpVec.push_back(ownCards[rightIdx]);
rightIdx++;
}
}
if (leftIdx > mid)
{
while (rightIdx <= right)
{
tmpVec.push_back(ownCards[rightIdx]);
rightIdx++;
}
}
else
{
while (leftIdx <= mid)
{
tmpVec.push_back(ownCards[leftIdx]);
leftIdx++;
}
}
for (int i = 0; i < tmpVec.size(); i++)
{
ownCards[left + i] = tmpVec[i];
}
}
void MergeSort(int left, int right)
{
if (left >= right) return;
int mid = (left + right) / 2;
MergeSort(left, mid);
MergeSort(mid + 1, right);
MergeResult(left, mid, right);
}
bool FindNumber(int num)
{
int left = 0;
int right = ownCards.size() - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (num > ownCards[mid])
{
left = mid + 1;
}
else {
right = mid - 1;
}
if (num == ownCards[mid])
{
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
int tmp;
ownCards.resize(N);
for (int i = 0; i < N; i++)
{
cin >> tmp;
ownCards[i] = tmp;
}
MergeSort(0, N-1);
int M;
cin >> M;
Find.resize(M);
for (int j = 0; j < M; j++)
{
cin >> tmp;
Find[j] = tmp;
}
for (int i = 0; i < M; i++)
{
bool b = FindNumber(Find[i]);
cout << b << " ";
}
}
반응형