[백준/실버] 1920번 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

1920번 실버4 수 찾기

 

~ 언제나처럼 문제 스포일러(??)를 포함하고 있습니다 ~

 

2진 탐색은 공부를 한 터라 보자마자 감이 바로 왔는데

시간 뚫는데 생고생을 다 했다.

어제 푼 문제는 쉽게 풀려서 아 오늘도 삘이 좋다 이러고 있었는데

응 아니야~ ㅠ

 

그냥 대충 2진서치 구현한 뒤 제출했는데 TO가 떠서

1. 반복문 하나 덜 쓰면 되지~ 하고 main에서 줄였는데도 꽝

2. vector 안쓰고 바로 보내면 되지~ 하고 줄였는데 꽝

여기까지는 금방 생각나서 고쳤는데 그 다음에서 좀 해멨다

 

cin이 더 빠를수도 있나 (아니란걸 알고 있었지만서도) 하고 tie(0)먹여서도 해보고

sort가 혹시 느린가 하고 검색해봤다가 C++은 C에 비해 완전 빠르다는 것도 배우고 오고

 

결국 찾은 정답은 매개변수 차이.

값을 복사하는데 있어서도 많은 시간 차가 나는 모양이다.

수가 많아질수록 당연히 그러겠지만, 일반적으로 코드를 구현할 때 그 부분은 생각을 못하고 있었다.

(보통 알고리즘에만 신경쓰기에...)

 

원래는 binarySearch()함수에 middle이라는 변수를 하나 더 써서 만들었는데

없는 버전으로 수정하니 (이후 오타가 있던터라 헤매긴 했지만) 바로 통과되었다.

 

으으.. 힘들었다.. 풀면서 "백준신이시어 뭐가 잘못된겁니까" 를 나도 모르게 외쳐버렸다.

아무래도 믿는 신이 하나 생긴 것 같다.

 

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

vector<int> arr;
//vector<int> seek; //long long으로?

//1이면 찾았음 0이면 몬찾았음
int binarySearch(int seek, int left, int right) {

	if (left > right) return 0; //맨 왼쪽(최소)이 크면 목록에 없는 것

	else {
		int mid = (left + right) / 2;
		if (arr[mid] == seek) return 1; //찾음 ㅎㅎ
		else if (arr[mid] > seek) {
			return binarySearch(seek, left, mid-1);
		}
		else { //arr[mid] < seek
			return binarySearch(seek, mid+1, right);
		}
	}
}

int main(void) {

	int inputN;
	scanf("%d", &inputN);
	//cin >> inputN;

	int n; 
	for (int i = 0; i < inputN; i++) {
		scanf("%d", &n);
		//cin >> n;
		arr.push_back(n);
	}

	sort(arr.begin(), arr.end()); //이분탐색은 정렬되어 있어야 쓸 수 있음

	int seekN;
	scanf("%d", &seekN);
	//cin >> seekN;

	int res;
	for (int i = 0; i < seekN; i++) {
		scanf("%d", &n);
		//seek.push_back(n); //?? vector 하나 없애도 타임오버?

		//타임오버(1) --;; -> 따로 돌리던 for문 합쳐버림
		res = binarySearch(n, 0, inputN - 1); //right-1 해야 인덱스가 초과 x
		printf("%d\n", res);
		//cout << binarySearch(n, 0, inputN - 1) << "\n";
	}

	return 0;
}