[BOJ] 백준 #1920. 수 찾기 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1920

• 알고리즘 분류: 이분 탐색
• 난이도: Silver 4

 

 

💬 풀이

N개의 수들을 배열에 담고, 정렬하여 이분탐색 실시

 

 

<시행착오 시리즈>

1. 처음에는 N개의 수들을 벡터v에 담고, 단순히 선형탐색으로 했다가 시간초과 났었다.  👉🏻 틀린 코드 확인
2. 그래서 이분탐색으로 했는데도, 이분탐색 함수 파라미터로 벡터 전체를 넘기니까 또 시간초과가 떴다.  👉🏻 틀린 코드 확인
3. 그래서 벡터 크기를 동적으로 하지 않고 전역으로 뺀 다음 v(100001)을 할당했다. 이때 sort(v.begin(), v.end())가 아니라 i=0부터 i=N-1까지만 부분정렬을 해야 했는데, 할 줄 몰라서 틀렸다. (sort(v, v+N)은 안되더라.)  👉🏻 틀린 코드 확인
4. 그래서 최종적으로 int타입 전역 배열 arr에 담는 걸로 바꾸고, sort(arr, arr+N) 해줘서 해결했다.

 

 

 

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int arr[100001];

int binarySearch(int target) {
	int st = 0;
	int en = N - 1;
	int mid;
	while (st <= en) { // start와 end가 역전되면 target이 존재하지 않음을 의미한다.
		mid = (st + en) / 2;
		if (target == arr[mid]) return 1;
		else {
			if (target < arr[mid]) en = mid - 1;
			else st = mid + 1;
		}
	}
	return 0;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N); // 정렬

	cin >> M;
	int num;
	while (M--) {
		cin >> num;
		cout << binarySearch(num) << '\n';
	}

	return 0;
}