[백준] 1920 수 찾기 Python

1. 문제 

n 개의 정수 a[] 와 m 개의 정수 arr[] 가 주어졌을 때,
arr[] 의 각 정수 X 가 a[] 안에 존재하는지 찾는 프로그램

 

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

2. 알고리즘 분류

* 자료 구조 

* 정렬 

* 이분 탐색 

* 해시를 사용한 집합과 맵 

 

3. 접근 방식

얼마 전에 ㅅㅎ님과 스터디하면서 같이 공부했던 이분 탐색과

Quick Sort, Merge Sort 에서 배운 left, right 를 활용해 보기로 했다

이분 탐색을 진행하기 전에 순서 정렬 먼저 하기! 
sort() sorted() 공부 자료 https://helloahram.tistory.com/entry/TIL-sorted

 

4. 전체 코드

# m 개의 정수 X 가 n 개의 정수 a [] 안에 존재하는지 찾는 프로그램 

# n, a, m, arr 입력 받기 
N = int(input())
A = [int(i) for i in input().split()] 

# N개의 정수가 입력되지 않으면 오류 발생
if len(A) != N:
    raise ValueError(f"Expected {N} integers, but got {len(A)}.")

M = int(input())
arr = [int(i) for i in input().split()]

# M개의 정수가 입력되지 않으면 오류 발생
if len(arr) != M:
    raise ValueError(f"Expected {M} integers, but got {len(arr)}.")

result = []

# a 를 이분 탐색으로 나누기 전에 먼저 정렬부터 하기
A.sort()

def binarySearch(x, left, right, A):

    while left <= right:
        mid = (left + right) // 2

        if x == A[mid]:
            return 1
        elif x < A[mid]:
            right = mid - 1
        elif x > A[mid]:
            left = mid + 1 

    return 0

for x in arr:
    result.append(str(binarySearch(x, 0, len(A)-1, A)))

print(" ".join(result))

 

위의 코드는 진행하는 순서대로 변수를 설정해서 가독성은 좋을 수 있지만

binarySearch 함수와 Main 이 뒤섞여 있는게 마음이 불편해서

함수 영역과 Main 영역을 깔끔하게 분리했다

# m 개의 정수 X 가 n 개의 정수 a[] 안에 존재하는지 찾는 프로그램 
# x 찾을 정수 left 왼쪽 경계 right 오른쪽 경게 


# 이분 탐색 함수 
def binarySearch(x, left, right, a):
    while left <= right:
        # a 의 중간값 계산 
        mid = (left+right) // 2

        # 값을 찾은 경우 1 반환
        # 찾는 값이 더 크면 오른쪽 반, 작으면 왼쪽 반 탐색 
        if x == a[mid]:
            return 1
        elif x > a[mid]:
            left = mid+1
        elif x < a[mid]:
            right = mid-1

    # 값을 찾지 못한 경우 0 반환
    return 0


if __name__ == '__main__':
    # n 배열의 크기, a n 개의 정수 배열 입력 받기 
    n = int(input())
    a = [int(i) for i in input().split()]

    # a 에 n 개의 정수가 입력되지 않으면 오류 발생
    if len(a) != n:
        raise ValueError(f"Expected {n} integers")

    # m 배열의 크기, arr m 개의 정수 배열 입력 받기 
    m = int(input())
    arr = [int(i) for i in input().split()]

    # arr 에 m 개의 정수가 입력되지 않으면 오류 발생
    if len(arr) != m:
        raise ValueError(f"Expected {m} integers")
    
    # n = 5
    # a = [5, 1, 4, 2, 3]
    # m = 5
    # arr = [1, 3, 7, 5, 9]

    # a 배열을 이분 탐색으로 나누기 전에 먼저 오름차순 정렬부터 하기
    a.sort()
    result = []

    # arr 의 각 정수에 대해 이분 탐색 수행하여 결과 저장하기 
    for x in arr:
        result.append(str(binarySearch(x, 0, len(a)-1, a)))

    # 결과를 공백으로 구분하여 출력 
    print(' '.join(result))

 

그런데 예상 출력은 줄바꿈이고, 나의 결과는 공백으로 구분하여 한 줄인데 정답이라고 한다 

답은 잘 나왔으니 된건가ㅎㅎㅎㅎ 

 

5. 이분 탐색

ㅅㅎ님의 스터디 자료가 더 잘 정리되어 있지만

나도 이분 탐색에 대해 정리해 보았다

* 이분 탐색 공부 자료