[백준] 1920번: 수 찾기 / C++ / 이분탐색

풀이 문제 : 백준 1920번 수 찾기
풀이 언어 : C++
알고리즘 : 이분탐색
문제링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

문제요약

---

배열 N, M 두개를 받고 M배열에 N배열 안에 존재하는 지 확인하는 문제다.

 

접근 방식

---

처음엔 간단히 이중 for문으로 구성했더니 시간초과가 나왔다.
각 배열 크기가 최대 100,000라서 2중 for문 돌리면 1초가 훌쩍 넘기 때문이다.

그래서 이분 탐색으로 구성했더니 100프로에서 틀렸습니다가 나왔다.
"모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다." 라는 조건 때문에
mid 값을 구하는 과정에서 int 범위가 벗어날 수 있다. 그래서 long long 으로 선언해야한다.

출처 : https://learn.microsoft.com/ko-kr/cpp/cpp/data-type-ranges?view=msvc-170

 

코드

---

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

int n, m;
long long an[100001];
long long am[100001];

void bs(long long in) {
	long long left = 0;
	long long right = n-1;
	while (left <= right) {
		long long mid = (long long)(left + right)/2;
		if (in == an[mid]) {
			cout << 1;
			return;
		}
		else if (in < an[mid]) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << 0;
	return;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> an[i];
	}
	sort(an, an + n);
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> am[i];
	}
	for (int i = 0; i < m; i++) {
		bs(am[i]);
		cout << '\n';
	}
	return 0;
}

 

회고

---

간단한 문제라고 생각했는데도 조건 때문에 꽤 까다로웠다.
조건을 꼼꼼히 파악하고 시간 복잡도도 계산해서 설계하는 것이 효율적일 것 같다.