문제

https://www.acmicpc.net/problem/10815
그렇게 어려운 문제는 아니었다. 근데 왜 난 이렇게 헤맸지

풀이

Aha! (핵심)

  • 정렬 후 이분탐색
  • 이분탐색 구현할 때
    • [방법1] 재귀 이용
    • [방법2] 반복문 이용

어려웠던 점

  • 시간초과가 나길래 처음에는 재귀를 써서 그런가 했는데, 그건 아닌가보다.
    두 방법 모두 다음 코드를 안 쓰면 시간초과가 나고, 쓰면 맞았습니다!가 뜬다.
ios_base::sync_with_stdio(0);
cin.tie(NULL);
  • 처음에 이분탐색 구현할 때 right = mid;로 해서 틀렸다.
    • (이러면 left==right이고 n != v[mid]인 경우에,
      아무것도 return 하지 않고,
      계속 left, right가 x, x인 상태를 벗어나지 못한다.)
    • --> right = mid - 1;이어야 함.
      (그래야 left, right가 x, x-1이 되어서 return 0 하고 끝남.)

코드

방법1 : 재귀 이용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int binarySearch(int n, vector<int> &v, int left, int right) {
	if(left > right)
		return 0; //못 찾았음

	int mid = (left + right) / 2;
	if (n == v[mid])
		return 1; //찾았음
	if (n < v[mid])
		return binarySearch(n, v, left, mid - 1);
	if (n > v[mid])
		return binarySearch(n, v, mid + 1, right);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int N; cin >> N;
	vector<int> num(N); //숫자 카드의 값들

	/*입력받기*/
	for(int i =0; i < N; i++) {
		cin >> num[i];
	}

	/*정렬하기*/
	sort(num.begin(), num.end());

	/*탐색하기*/
	int M; cin >> M;
	int input;
	while (M--) {
		cin >> input;
		cout << binarySearch(input, num, 0, N - 1) << " ";
	}

	return 0;
}

방법2 : 반복문 이용

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int binarySearch(int n, vector<int> &v, int left, int right) {
	while (left <= right) {
		int mid = (left + right) / 2;
		if (n == v[mid])
			return 1; //찾았음
		if (n < v[mid])
			right = mid - 1;
		if (n > v[mid])
			left = mid + 1;
	}
	return 0; //못 찾았음
}


int main() {
	//방법1과 완전히 동일
}

0개의 댓글

Powered by GraphCDN, the GraphQL CDN