백준 10815 숫자 카드

 

탐색을 할때 가장 좋은 방법 중 하나는 dictornary를 이용하는 것이다. 

탐색의 경우, 리스트라면 시간 복잡도는 $ O(n) $ 이다.

다만, dict과 set의 경우 시간 복잡도는 $ O(1) $ 이다. 

 

상근이의 카드 배열을 dict으로 만든 다음

dict[상근의 카드] = 아무 숫자로 등록

하여, dict.keys()에 내 카드가 있다면 1을 출력하도록 한다. 

import sys
input = sys.stdin.readline

N = int(input())
cards = list(map(int,input().split()))

M = int(input())
checks = list(map(int,input().split()))


_dict = {}

for i in range(len(cards)):
    _dict[cards[i]] = 0 

for j in range(M):
    if checks[j] not in _dict.keys():
        print(0)
    else:
        print(1)

 

두 번째 방법은 이진 탐색을 하는 것이다.

이진 탐색을 해본적이 없기 때문에, 이진 탐색에 대한 공부를 이참에 같이 해보도록 한다. 

 

Binary search

• 시간 복잡도 : $ O(log(N))
• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 주의 사항 : 먼저 sorted된 자료에 대해 진행해야 한다.

필요한 Parameter

• target : 찾고자 하는 값 
• data : 정렬된 리스트
• start : 정렬된 리스트의 처음 값 인덱스
• end : 정렬된 리스트의 마지막 값 인덱스
• mid : start, end의 중간 인덱스 

 

구현방법

정렬된 자료의 mid 값 = target 이냐 ?? 를 탐색한다.

아니라면 start, end를 이동 

def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)

 

그럼 풀어보자

import sys
input = sys.stdin.readline

def binary_search(array, target, start, end):

    while start <= end:
        mid = (start+end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1 
    
    return None

N = int(input())
cards = list(map(int,input().split()))
M = int(input())
checks = list(map(int,input().split()))
cards.sort()

for check in checks:
    if binary_search(cards,check,0,N-1) is not None:
        print(1)
    else:
        print(0)