[python_파이썬_Pass]백준_10815번_숫자카드_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/YUFXMQL1DWY?feature=shared

이전에 해시를 이용한 방법으로 해결했으나 이진탐색 및 해시등 여러가지를 학습한 후 다시 풀어보았다.

학습내용 : https://heodinkcodingdiary.tistory.com/104

[python_파이썬_Pass]백준_1920번_수찾기_이분탐색_풀이

 

<첫번째 시도 : 맞았습니다.>

다른거 다 필요 없이 set을 활용해서 시간을 단축 할 수 있다. 

탐색을 할때는 최대한 집합(set)을 자주 활용해보자.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = set(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

for i in M_nums:

    print(int(i in N_nums), end = ' ')

1. List (리스트)

리스트는 순차적인 데이터 구조로, 인덱스를 통해 값에 접근할 수 있지만, 특정 값을 찾는 경우에는 순차 탐색을 해야 합니다. 즉, 리스트는 첫 번째 요소부터 끝까지 하나씩 비교하며 값을 찾아야 하기 때문에 **시간 복잡도가 O(N)**입니다. 리스트에서 하나의 요소를 찾는 데 걸리는 시간은 데이터가 많아질수록 선형적으로 증가합니다.

2. Set (집합)

반면에, set은 해시 테이블을 기반으로 구현되어 있어, 값의 중복을 허용하지 않으며 순서가 없다는 특징이 있습니다. 하지만 특정 값을 찾는 경우에는 상수 시간에 조회할 수 있습니다. 이는 내부적으로 해시 함수를 이용해 값을 저장하고, 그 값을 검색할 때도 해시를 이용해 즉시 값을 찾을 수 있기 때문입니다. 따라서 set에서 값을 찾는 시간 복잡도는 **O(1)**입니다.

 

<두번째 시도 : 맞았습니다.>

해시를 이용해서 해결했다. 

딕셔너리를 활용할 때 get라이브러리를 활용하면 깔끔하게 코드를 만들 수 있다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

N_dict = {}

for i in N_nums:

    N_dict[i] = 1

for i in M_nums:

    if i in N_dict:

        print(N_dict[i], end = ' ')

    else:

        print(0, end = ' ')

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {N_nums[i] : 1 for i in range(len(N_nums))}

for i in M_nums:

    print(answer.get(i, 0), end = ' ')

 

<세번째 시도 : 맞았습니다.>

이진탐색을 통해서 해결했다. 이제 조금 감이 잡힌다.

그런데 해시를 이용한 방법 대비 효율이 너무 떨어진다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

N_nums.sort()

def Binary(arr, m):

    start, end = 0, len(arr) - 1

   

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] == m:

            return 1

        elif arr[mid] > m:

            end = mid - 1

        else:

            start = mid + 1

    return 0

for i in M_nums:

    print(Binary(N_nums, i), end = ' ')

 

<네번째 시도 : 맞았습니다.>

이진탐색 재귀함수형태로 해결했다. 이것도 조금 감은 잡히네.

while과 재귀의 차이네.

while에서는 내부에 return이 2번인데,

재귀에서는 범위내에 맞는 것이 없으면 다 돌고 최종 start > end가 만족되어 0이 반환되는 구조네.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

N_nums.sort()

def Binary(target, start, end):

    if start > end:

        return 0

   

    mid = (start + end) // 2

    if N_nums[mid] == target:

        return 1

    elif N_nums[mid] > target:

        end = mid - 1

    else:

        start = mid + 1

   

    return Binary(target, start, end)

for i in M_nums:

    print(Binary(i, 0, N - 1), end = ' ')