https://www.acmicpc.net/problem/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)
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[프로그래머스] Lv1 문제풀이 (0) | 2023.10.09 |
---|---|
[백준] 1937번 욕심쟁이판다 - 파이썬 (0) | 2023.10.06 |
[백준] 2805번 나무자르기 - 파이썬 (1) | 2023.10.06 |
[백준] 2606번 바이러스 - 파이썬 (2) | 2023.10.05 |
다이나믹 프로그래밍 - 파이썬 (1) | 2023.10.05 |