[이분 탐색] 숫자카드 (boj.kr/10815)

숫자카드 (boj.kr/10815)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 10815 숫자 카드

int main(){
	int n, m;
	
	scanf("%d", &n);
	
	vector<int> num(n);
	for(int i = 0; i < n; i++) scanf("%d", &num[i]);
	
	sort(num.begin(), num.begin() + n);
	
	scanf("%d", &m);
	
	for(int i = 0; i < m; i++){
		int x;
		scanf("%d", &x);
		
		int left = 0;
		int right = n - 1;
		bool flag = false;
		
		while(left <= right){
			int mid = (left + right) / 2;
			
			// 기저 사례 : mid 값과 x 가 같으면 찾음
			if(num[mid] == x){
				flag = true;
				break;
			}
			
			else if(num[mid] < x){
				left = mid + 1;
			}
			else{
				right = mid - 1;
			}
		}
		printf("%d ", flag ? 1 : 0);
	}
	printf("\n");
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 이분 탐색을 바로 적용한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 입출력 형식의 중요성

- cin / cout 보다 scanf printf 가 속도가 더 빠르다는 것은 자명하다. 이것을 인지하지 못하고 고수준 입출력을 사용한다면, 시간 초과가 나온다. tk 의 크기가 매우 크기 때문에 이런 것 하나하나가 맞고 틀림을 좌지우지 함을 인지하자.