백준 집합과 맵 단계 : 1815번 숫자 카드

🛎️ 1815번 숫자 카드

📌 메모리와 시간을 아껴라!!

선형 탐색 보다는 이진 탐색을

선형 탐색은 알고리즘이 맞아도 시간이 오래걸려 시간초과로 통과할 수 없었다.

이진 탐색은 정렬이 필수!!

➕ 일반 입력 보다는 stdin을 ..?

😅 생각보다 별로 차이는 없었다...ㅎ 파이썬은 입력에 큰 시간이 걸리지 않는 듯?

stdin으로 하나 입력 받기

from sys import stdin

x1 = int(stdin.readline())

stdin으로 한 줄 입력 받기

from sys import stdin

a_list = list(map(int,stdin.readline().split()))

모듈 쓰지 않고 int 형 리스트 받기

a_list = [int(i) for i in input_list.split(" ")]

정답 코드

def binary_search(a_list,n):
    first = 0
    last = len(a_list) - 1
    while first <= last:
        mid = (first+last)//2
        if a_list[mid] == n:
            return 1
        elif a_list[mid] < n:
            first = mid +1
        else:
            last = mid -1
    return 0

def sort(a_list):
    if len(a_list) <= 1 :
        return a_list
    mid = len(a_list)//2
    left_list = a_list[:mid]
    right_list = a_list[mid:]
    left_list = sort(left_list)
    right_list = sort(right_list)

    a_index = 0
    left_index = 0
    right_index = 0

    while left_index < len(left_list) and right_index < len(right_list):
        if left_list[left_index] <= right_list[right_index]:
            a_list[a_index] = left_list[left_index]
            left_index += 1
        else:
            a_list[a_index] = right_list[right_index]
            right_index += 1
        a_index += 1

    while left_index < len(left_list):
        a_list[a_index] = left_list[left_index]
        left_index += 1
        a_index += 1

    while right_index < len(right_list):
        a_list[a_index] = right_list[right_index]
        right_index += 1
        a_index += 1

    return a_list


x1 = int(input())
input_list = input()
a_list = [int(i) for i in input_list.split(" ")]
a_list = sort(a_list)

x2 = int(input())
input_list = input()
t_list = [int(i) for i in input_list.split(" ")]


y_list = []
for i in t_list:
    y_list.append(binary_search(a_list,i))

y_str = ' '.join(str(i) for i in y_list)

print(y_str)

🤔 파이썬에는 정렬 함수가 있네,,?

꿀이당 🍯 메모리도 1/3로 단축되었다. (메모리는 아주 살짝 늘어남)

def binary_search(a_list,n):
    first = 0
    last = len(a_list) - 1
    while first <= last:
        mid = (first+last)//2
        if a_list[mid] == n:
            return 1
        elif a_list[mid] < n:
            first = mid +1
        else:
            last = mid -1
    return 0

from sys import stdin
x1 = int(stdin.readline())
a_list = list(map(int,stdin.readline().split()))
a_list.sort()

x2 = int(stdin.readline())
t_list = list(map(int,stdin.readline().split()))



y_list = []
for i in t_list:
    y_list.append(binary_search(a_list,i))

y_str = ' '.join(str(i) for i in y_list)

print(y_str)