수 찾기 [ Python ] [ 백준 : 1920 ]

---

풀이 및 회고

 

이분 탐색에 대해 공부할 수 있는 문제이다. 문제를 읽고 이분 탐색을 공부했다.

정렬된 값의 가운데 값을 기준으로 찾을 값 보다 적은지 큰지를 비교하며 찾아내는 알고리즘이었다.

문제는 1 3 7 9 5 를 찾는데 4 1 5 2 3 중에 1 이 포함되어 있다면 1을 출력하고 3이 포함되어 있으면 1을 출력하고 7이 포함되어 있지 않으므로 0 을 출력하고 9 가 포함 안되있기 때문에 0 을 출력하고 5 가 포함되어 있어 1 을 출력한다.

처음 해본 탐색문제인데 어려웠으나 메모리를 줄이는 과정이 즐거웠다. 

이런 탐색을 어디에 활용하는지 알아보니 더 흥미로웠다. 잘은 모르지만 나중에 검색같은걸 구현할때도 활용하면 데이터를 쓸데없이 탐색하는 일을 줄일 수 있을 것같다. 

# 수 찾기

#알고리즘
# 1. n을 입력받는다.
n = int(input())
# 2. A 를 리스트 형태로 n 만큼 입력받는다.
A = list(map(int, input().split()))
# 3. m 을 입력받는다.
m = int(input())
# 4. B 를 리스트 형태로 m 만큼 입력받는다.
B = list(map(int, input().split()))
# 5. A 를 sort 로 정렬한다
A.sort()
# 6. for 문 선언해 인덱스 값을 확인한다.
answer = []
for b in B:
    start,end = 0,n-1
    # while 문 선언 start 와 end 변수를 이용해 탐색을 구현
    while start <= end:
        # 7. n 의 중간값을 찾고, middle 이란 변수에 저장한다.
        middle = (start + end) // 2
        # 찾고자 하는 b 의 값이 A[middle] 과 같다면 answer 리스트에 추가하고 break 를 통해 while 문을 탈출한다.
        if A[middle] == b:
            answer.append(1)
            break
        # 8. 찾고자 하는 b의 값이 middle 보다 적다면 앞의수를 확인한다.
        elif A[middle] > b:
            end = middle - 1
        # 9. 찾고자 하는 m의 값이 middle 보다 크다면 뒤의수를 확인한다.
        else:
            start = middle + 1
    else: # 찾고자 하는 값이 없다면 0 을 추가한다
        answer.append(0)
# 출력한다.
for ans in answer:
    print(ans)

탐색문제 재밌숨