숫자 카드 풀이

문제 링크: https://www.acmicpc.net/problem/10815

백준 집합과 맵 1단계 - 10815번 숫자 카드를 풀어보았다.

 

풀이: 이진탐색을 써서 풀면 된다.

C++의 경우 algorithm 헤더가 제공하는 이진 탐색 함수를 이용했다.

파이썬의 경우, if bisearch(card,num[i],0,n-1) is not False: print(1,end=' ') 에서 is not을 안 쓰고 != 쓰면 틀렸다고 나왔다. 찾아보니 ==는 값을 비교하고, is는 객체를 비교한다고 나왔다. is는 none, false, true 등을 비교할 때만 써야 할 거 같다.

 

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  int n,m,a;
	cin>>n;
	vector<int>nv;
	vector<int>mv;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		nv.push_back(a);
	}
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a;
		mv.push_back(a);
	}
	sort(nv.begin(),nv.end());
	for(int i=0;i<m;i++)
	{
		if (binary_search(nv.begin(),nv.end(),mv[i])) cout<<1<<" ";
		else cout<<0<<" ";
	}
}

Python

def bisearch(arr,target,start,end): # 이진탐색
	while start<=end:
		mid=(start+end)//2
		if arr[mid]==target:
			return mid
		elif arr[mid]>target:
			end=mid-1
		else: start=mid+1
	return False # 없으면 false

n=int(input())
card=list(map(int,input().split()))
m=int(input())
num=list(map(int,input().split()))
card.sort() # 이진탐색 쓸꺼면 정렬해줘야한다
for i in range(m):
	if bisearch(card,num[i],0,n-1) is not False: print(1,end=' ')
	else: print(0,end=' ')

Java