[백준] 수 찾기

문제

백준 수 찾기 https://www.acmicpc.net/problem/1920

 

코드

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

for target in targets:
    answer = 0
    
    # 이분탐색
    s = 0
    e = n - 1

    while s <= e:
        mid = (s + e) // 2

        if arr[mid] == target:
            answer = 1
            break
    	elif arr[mid] > target: # 다운?
            e = mid - 1
        else:	# 업?
            s = mid + 1

    print(answer)

 

풀이

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

입력 형식에 맞게 변수들을 입력받는다.

targets에 있는 값들이 arr에 있는지 이분탐색하며 찾을것이기 때문에 arr은 오름차순 정렬해둔다.

 

for target in targets:

타겟들 마다 arr에 있는지 없는지에 대한 값을 반환해야하므로 반복문을 사용한다.

반복문으로 각각의 target에 대해 이분탐색을 진행한다.

 

answer = 0

# 이분탐색
s = 0
e = n - 1

while s <= e:
    mid = (s + e) // 2

    if arr[mid] == target:
        answer = 1
        break
    elif arr[mid] > target: # 다운?
        e = mid - 1
    else:	# 업?
        s = mid + 1

target이 arr 배열에 있는지 없는지에 대한 변수, answer을 선언한다.

 

이분 탐색을 하며 배열에 있는지 없는지 탐색한다.

시작점(s)와 끝점(e)를 선언하고

target 값을 끝까지 못찾는다면 시작점(s)과 끝점(e)이 교차되는 순간이 올것이다. 교차되는 순간까지 계속 이분탐색한다.

 

arr의 중간지점 값이 target값과 같다면 즉, target이 arr안에 있다면 answer을 1로 초기화하고 이분탐색을 멈춘다.

arr의 중간지점이 target보다 더 크다면 끝 지점을 mid - 1 로 줄이고, 다시 이분탐색한다.

arr의 중간지점이 target보다 더 작다면 시작 지점을 mid + 1로 늘리고, 다시 이분탐색한다.

 

print(answer)

이분탐색 완료 후 answer 값을 출력한다.

이분탐색 중 arr에서 target 값을 찾았다면 answer이 1로 초기화 되어 있을것이고, 못 찾았다면 처음 선언했던 0 그대로 일것이다.

 

다른 코드

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

for target in targets:
    if target in arr:
        print(1)
    else:
        print(0)

 

풀이

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

입력형식에 맞춰 입력받는 코드는 전 코드와 동일하다.

 

for target in targets:
    if target in arr:
        print(1)
    else:
        print(0)

더 직관적인 코드를 짜고 싶다면 배열안에 특정 원소가 있는지 확인하는 명령어를 사용하는 방법도 있다.

targets 배열을 돌며 

각 target이 arr안에 있다면 1을 출력하고, 아니라면 0을 출력한다.

 

하지만 배열에서 <in> 명령어는 O(n)의 시간 복잡도를 가지기때문에, 배열의 크기가 크다면 시간이 오래 걸린다는 단점이 있다.

실제로 약 26배나 늘어난 시간을 볼 수 있다.

 

새롭게 배운점 / 느낀점

• <in> 명령어가 O(n)의 시간복잡도를 가진다는것을 알게 되었다. 예전에는 <in>명령어를 쉽게 썼는데, 앞으로는 신경써서 써야할것 같다.
• 이분탐색으로 코드를 짜면 <in> 명령어를 사용할때보다 시간이 훨씬 빠르지만, 가독성은 비교적 매우 떨어진다. 그래서 이분 탐색 과정을 함수로 만들어서 함수명을 직관적이게 잘 지으면 실행속도도 챙기고 가독성도 챙길 수 있겠다는 생각을 했다.