[ BOJ 10815 ] 숫자 카드(Python)

문제

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

상근이는 n개의 카드를 가지고 있다.
이때 m개의 카드가 주어질 때 상근이가 갖고 있으면 1, 갖고있지 않으면 0을 출력하면 된다.

문제 풀이

🌲 이진 탐색 트리

전에 배웠던 이진 탐색 트리를 이용해서 문제를 풀어보고 싶었다, , , 🙂

1. tree 형태를 클래스로 정의하기

class Tree:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 배열을 이진 탐색 트리로 만드는 함수 정의하기

def toBST(lst):
    if not lst:
        return None

    mid = len(lst) // 2

    node = Tree(lst[mid])
    node.left = toBST(lst[:mid])
    node.right = toBST(lst[mid + 1:])

    return node


BST = toBST(sorted(cards))

3. 이진 탐색 트리를 이용해서 탐색하기

• 체크해야 할 값이 현재 위치의 값보다 작으면 right로, 현재 위치보다 크면 left로 이동해주었다.
• 체크값을 찾으면 flag를 True로 바꾸어주었고, 더 이상 이동할 수 없으면 flag는 False 값 그대로이다.
• flag에 따라 결과값을 출력을 해주었다.

for c in check:
    curr = BST
    curr_val = curr.val
    flag = False

    while curr is not None:
        curr_val = curr.val
        if curr_val < c:
            curr = curr.right
        elif curr_val > c:
            curr = curr.left
        else:
            flag = True
            break
    if flag:
        print(1,end=' ')
    else:
        print(0,end=' ')
print()

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int, input().rsplit()))

m = int(input())
check = list(map(int, input().rsplit()))

class Tree:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def toBST(lst):
    if not lst:
        return None

    mid = len(lst) // 2

    node = Tree(lst[mid])
    node.left = toBST(lst[:mid])
    node.right = toBST(lst[mid + 1:])

    return node


BST = toBST(sorted(cards))    

for c in check:
    curr = BST
    curr_val = curr.val
    flag = False

    while curr is not None:
        curr_val = curr.val
        if curr_val < c:
            curr = curr.right
        elif curr_val > c:
            curr = curr.left
        else:
            flag = True
            break
    if flag:
        print(1,end=' ')
    else:
        print(0,end=' ')
print()

2️⃣ 이진 탐색

1. 배열 정렬하고, 범위 정하기

cards.sort()
l, r = 0, n-1

2. 중간값 비교해주기

mid = (l + r) // 2

3. 중간값이 찾는 값보다 작을 경우

if cards[mid] < c:
    l = mid + 1

4. 중간값이 찾는 값보다 클 경우

elif cards[mid] > c:
    r = mid - 1

5. 중간값이 찾는 값과 같을 경우

else:
    flag = True
    break

전체 코드

import sys
input = sys.stdin.readline

# 상근이가 갖고 있는 숫자 카드 n개
# 체크 해야하는 숫자 카드 m개

n = int(input())
cards = list(map(int, input().rsplit()))

m = int(input())
check = list(map(int, input().rsplit()))

cards.sort()
l, r = 0, n-1

for c in check:
    l, r = 0, n-1
    flag = False
    while l <= r:
        mid = (l + r) // 2
        if cards[mid] < c:
            l = mid + 1
        elif cards[mid] > c:
            r = mid - 1
        else:
            flag = True
            break
    if flag:
        print(1,end=' ')
    else:
        print(0,end=' ')
print()

• 이진 탐색 트리를 직접 구현한 코드가 시간이 2배정도 더 걸렸다. 당연함.
• 결론
  정렬된 배열을 이용하면 이진 탐색 트리를 구현할 필요가 전혀 없다.
  그래도 복습했다. 사서 고생하자~!