[백준] 1920번 수 찾기

사용 언어 - Python3

1920번: 수 찾기 (실버4, 이분 탐색)

문제 ★이분 탐색 문제★

1920번: 수 찾기

 

 

정답

시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !!

(코드 풀이)

0. 이분 탐색 전 정렬하기

이분 탐색을 하기 위해선 탐색 기준이 정렬되어 있어야한다.

a를 정렬한 후 arr과 비교해야 a의 탐색 범위를 줄이는 의미가 있기 때문이다.

 

1. 시작/끝/중간 값 선언

n 범위 안에서 arr 값(num)이 있는 지 찾아야하기 때문에,

시작값은 0 / 끝값은 n-1 / 중간값은 (0+n-1)//2 로 선언한다.

 

2. 중간값과 비교하며 찾기

시작값 <= 끝값이라면, num == a[mid] 일 때까지 시작, 끝값을 1 증가/감소하면서 범위를 줄인다.

시작값 <= 끝값 일 때까지 범위를 줄여야하기 때문에, while문을 사용한다.

 

3. 예외 처리

범위 안에 값을 찾지 못한다면, 0을 프린트해줘야한다.

isExist 라는 True or False 변수를 활용하여 false일 때만 0을 프린트해준다.

# 정답1 - 이분탐색

n = int(input())
a = list(map(int,input().split()))
m = int(input())
arr = list(map(int,input().split()))
a.sort()

for num in arr:
    start,end = 0,n-1
    isExist = False

    while start<= end:
        mid = (start+end)//2
        if num == a[mid]:
            isExist  = True
            print(1)
            break
        elif num > a[mid]:
            start = mid+1
        else:
            end = mid-1
            
    if not isExist:
        print(0)

 

이분 탐색으로 하지 않고, min/max 함수를 사용했더니 시간 초과로 오답이 나왔다.

# 오답 - 시간 초과

n = int(input())
a = list(map(int,input().split()))
m = int(input())
arr = list(map(int,input().split()))

for num in arr:
    if num >= min(a) and num <= max(a):
        print("1")
    else:
        print("0")

a를 정렬하지 않고 list 대신 set했다. min, max를 사용하지 않고 num이 a에 있는지 하나씩 비교했더니 오답은 아니었다.

# 정답2 - 이분탐색 X

n = int(input())
a = set(map(int,input().split()))
m = int(input())
arr = list(map(int,input().split()))

for num in arr:
    if num in a:
    	print(1)
    else:
    	print(0)

 

---

레퍼런스

• 정답 참고

[BOJ] 백준 1920번 수 찾기 (Python)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부