ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

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

Posted on Feb 12, 2021 #이진 탐색(Binary Search)   #Algorithm   #C/C++  

1920 | 수 찾기

🙋‍♀️ 문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

🙋‍♂️ 예제 입출력

5
4 1 5 2 3
5
1 3 7 9 5

1
1
0
0
1

🚀 코드

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;

int find(int len, int x) {
	// 이진 탐색
	int lo = 0;
	int hi = len - 1;
	int mid = 0;
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (v[mid] == x) {
			return 1;
		}
		else if (v[mid] > x) {
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}
	}
	return 0;
}

int main() {
	int n = 0;
	int m = 0;
	scanf("%d", &n);
	int x = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	scanf("%d", &m);
	int len = v.size();
	for (int i = 0; i < m; i++) {
		scanf("%d", &x);
		int flag = find(len, x);
		printf("%d\n", flag);
	}

	return 0;
}

🌠 메모

시간 제한이 조금 빡세서 algorithm의 find를 써도 시간 초과가 났다. 결국 이진 탐색을 사용했다.

이진 탐색은 다음 포스팅에서 자세하게 다루었으니 필요시 참고하자.

이진 탐색을 사용해도 계속해서 시간 초과가 나서 꽤나 애먹었던 문제이다. 자주 놓치는 부분일 것 같아 이렇게 정리해 두겠다.

🚨 주의!

  • cin, cout 보다는 scanf, printf가 더 빠르다.
  • 부득이하게 cin, cout을 쓰고자 한다면, 
    ios_base::sync_with_stdio(false);
cin.tie(NULL);

    를 추가해 주도록 하자. 그러나 위의 코드를 삽입한 후에는 c와 c++의 입출력을 섞어 쓰면 안된다. 싱크가 맞지 않아 입력 순서가 뒤바뀔 수 있기 때문이다.

  • 이렇게까지 했는데도 시간 초과가 날 땐, 배열을 전역변수로 빼도록 한다. 함수에서 호출할 때 시간을 많이 잡아먹는 것 같다.


# 카테고리