배열 A의 원소의 개수 N과 질문의 개수 M을 입력받은 후 그 크기를 이용해 배열 A와 질문들을 모아놓은 배열 D를 벡터를 이용해 선언했습니다. 이후 반복문을 통해 배열 A와 질문 D의 요소들을 차례대로 입력받았습니다. 문제에서 A의 원소들을 오름차순으로 정렬된 배열 B를 만드라고 했지만 메모리 공간 절약을 위해 새로운 배열을 만들지 않고 A를 그대로 사용했습니다. 이를 위해 sort함수를 이용해 A를 오름차순으로 정렬했습니다.
여기까진 쉽게 생각해냈는데 아래 반복문에서 시간이 오래 걸렸습니다. 처음에 이중 반복문을 이용해 앞에서부터 배열의 요소를 순차적으로 탐색했습니다. 그렇게 풀었더니 답은 나오는데 시간 초과가 떴습니다. 구글링을 통해 제가 푼 방식은 선형 탐색으로 탐색 알고리즘의 가장 기초가 되는 알고리즘으로 구현하긴 매우 쉽지만 데이터의 크기가 커질수록 찾는 시간이 오래 걸린다는 단점이 있다는 것을 알게 되었습니다. 선형 탐색의 경우 최악의 경우 마지막 요소까지 탐색해야 하기 때문입니다.
선형 탐색 대신 이분 탐색을 사용하기로 했습니다. 이분 탐색은 탐색할 범위를 절반으로 줄여서 탐색하기 때문에 선형 탐색보다 훨씬 빠르게 탐색할 수 있었습니다. 이분 탐색의 원리를 이해하기 위해 수를 하나하나 넣어 여러 경우의 수를 생각해보았었는데 그것보단 언어적으로 이해하는 편이 쉬웠습니다. 이분 탐색을 간단히 설명하자면 up/down 게임과 비슷하다고 할 수 있습니다. up/down 게임은 예를 들어 1~100까지의 수 중 상대가 생각한 숫자가 73이라면 이를 맞추는 게임인데 학창 시절 한 번쯤 경험해봤으리라 생각합니다. up/down게임을 이기기 위한 전략은 가운데 숫자를 이용하는 것입니다. 이분 탐색은 이와 같이 가운데 숫자보다 큰지 작은 지를 고려해 찾아야 하는 숫자를 탐색해나갑니다.
이분 탐색 코드를 이용하니 시간 초과가 뜨지 않고 문제를 맞힐 수 있었습니다. 이외에 추가적으로 작성해준 것은 check 변수인데 이 문제의 경우 탐색하는 수가 없는 경우도 찾아내야 하기 때문에 탐색하는 수를 찾았을 때 check 변숫값을 false에서 true로 변경해주었습니다. check 값이 false면 탐색하는 수를 찾지 못한 경우이므로 -1을 출력했고 check 값이 true면 탐색하는 수를 찾은 경우이므로 찾아낸 위치를 출력해줬습니다.
•
내 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N, M; //배열A의 원소의 개수N, 질문의 개수 M
cin >> N >> M;
vector<int>A(N); //배열 A(B의 역할까지 수행)
vector<int>D(M); //M개의 질문에 대해서 주어진 D
for (int i = 0; i < N; i++)
{
cin >> A[i];
}
for (int i = 0; i < M; i++)
{
cin >> D[i];
}
sort(A.begin(), A.end()); //오름차순으로 정렬
//선형탐색
/*
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (D[i] == B[j])
{
printf("%d\n", j);
break;
}
if (j == N - 1)
{
printf("-1\n");
}
}
}
*/
//이분탐색
for (int i = 0; i < M; i++)
{
int left = 0; //index에서 가장 왼쪽은 0임
int right = N - 1; //index에서 가장 오른쪽은 N-1임
int answer; //출력할 값
int mid; //가운데 값(이분탐색 알고리즘에 활용)
bool check=false; //탐색하려는 수가 없는 경우를 찾기 위함
while (left <= right)
{
mid = (left + right) / 2;
if (A[mid] < D[i])
{
left = mid + 1;
}
else
{
answer = mid;
right = mid - 1;
}
if (A[mid] == D[i])
{
check = true;
}
}
/*
탐색하려는 수가 없는 경우 -1을 출력, 아닌 경우 그 위치를 출력
*/
if (check)
{
cout << answer << "\n";
}
else
{
cout << -1 << "\n";
}
}
}
C++
복사