[백준] 10815번 숫자카드 - 파이썬

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

10815번: 숫자 카드

 

---

💡문제이해 : 주어진 수에 대해서 상근이 가지고 있는 카드 중 해당되는 숫자가 있으면 1, 없으면 0 출력 

🤔 풀이 : 완전탐색도 가능하겠지만 이분탐색을 이용하여 해결 

---

 

1. 주어진 수와 상근이 가지고 있는 카드 받아오기

n = int(input())
arr1 = list(map(int,input().split()))

m = int(input())
arr2 = list(map(int,input().split()))

 

2. 이분탐색을 이용하기 위해 주어진 수 오름차순으로 정렬 

arr1 = sorted(list(map(int,input().split())))

 

3.  상근이 가지고 있는 수와 비교 하기 위해 for문 사용, 처음과 끝 지점 설정 

for num in arr2 :
	
    s = 0
    e = n-1
    flg = False

 

4.   만일 중간지점이 상근이 가지고 있는 수와 동일 할 경우  True 반환, 아닐경우 처음 아니면 끝 지점 조정 

while e >= s :

	mid = (e+s) // 2
    
	if arr1[mid] == num :
        flag = True
        break 
        
	elif arr[mid] > num :
		e = mid -1 
        
	else :
       	s = mid+1

 

5. 상근이 가지고 있는 수 일 경우 1반환, 아닐 경우 0반환 

if flag :
    result.append(1)
else :
    result.append(0) 

print(*result)

6. 전체코드 

n = int(input())
arr1 = sorted(list(map(int,input().split())))

m = int(input())
arr2 = list(map(int,input().split()))

result=[]
for num in arr2 :
    s = 0 
    e = n-1
    flag = False

    while s <= e : #s와 e가 교차되지 않았다면

        mid = (s+e)//2

        #업인가요?다운인가요?정답인가요?

        if arr1[mid] == num :
            #정답입니다! 
            flag = True
            break

        elif arr1[mid] > num :
            e = mid - 1
        
        else :
            s = mid + 1 
    
    if flag :
        result.append(1)
    else :
        result.append(0)

print(*result)