(cpp)Baekjoon 10815번 문제 ‘숫자 카드’ - 자료구조, 정렬, 이분탐색

on Programming Languages

Baekjoon 10815번 문제 ‘숫자 카드’ - 자료구조, 정렬, 이분탐색

문제

문제풀이

image

코드

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

//숫자카드 N장
//정수 M개

int n, m, n_num[500001], m_num[500001];
int check[500001]={ 0,};
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> n_num[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> m_num[i];
	}
	
	//n_num : -10 2 3 6 10
	//m_num :10 9 -5 2 3 4 5 -10
	sort(n_num, n_num + n);
	
	
	
	for (int i = 0; i < m; i++) {
		int left = 0; //이 변수 선언부가 for문 안에 들어와야 됨
		int right = n - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (n_num[mid] == m_num[i]) {
				check[i] = 1;
				break;
			}
			if (n_num[mid] < m_num[i]) {
				left = mid + 1;
			}

			else if (n_num[mid] > m_num[i]) {
				right = mid - 1;
			}
		}

	}

	for (int i = 0; i < m; i++) {
		cout << check[i]<<' ';
	}
}
  • left가 right와 작거나 같은 경우 탐색 계속함
  • left, right 변수가 for문 안에 들어와 있어야 함
  • map으로 풀면 시간초과 발생