[Python] 백준 10815 숫자카드

지금 해빗프로젝트에서 7일간 뭐든 꾸준히 하기 챌린지를 하는 중이다

평소에 놓았던 알고리즘이나 시작해보자 해서 하는 챌린지 히히

이 문제를 택한 이유는 클래스101 코딩 인터뷰를 봤을 때 풀었던 문제랑 유사하기 때문에 그 때의 나를 기억하기 위해서 택했다.

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

 

접근 방식

1. 2중 포문을 돌려서 하나하나 있는지 검사하기

우선 제일 먼저 생각했던 접근 방법이다. 단순하게 배열의 숫자들이 있는지 검사하려면 하나하나 살펴보면 되잖슴

n = int(input())
card_list = list(map(int, input().split()))
m = int(input())
num_list = list(map(int, input().split()))

answer = [0 for _ in range(m)]

for i in card_list:
    for idx, j in enumerate(num_list):
        if i == j:
            answer[idx] = 1
            break

print(answer)

짜고 보니 파이썬에서 in 함수가 있는 것을 깜빡했다. 하지만 시간복잡도는 같으니 넘어가자 ㅎㅎ

시간 복잡도 : O(n2)

공간 복잡도 : O(n2)

 

 

2. 배열 탐색 돌리기 (이진 탐색)

n = int(input())
card_list = list(map(int, input().split()))
m = int(input())
num_list = list(map(int, input().split()))

answer = [0 for _ in range(m)]

card_list.sort()

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False

for idx, i in enumerate(num_list):
    if binary_search(card_list, i, 0, n-1) is not False:
        answer[idx] = 1

print(answer)

정말 오랜만에 이진탐색 코드를 짜봤다. 이렇게 하면 시간이 훨 줄어들 것

시간 복잡도 : O(nlogn)

공간 복잡도 : O(n)

 

 

3. dictionary를 만들어서 검사하기

n = int(input())
card_list = list(map(int, input().split()))
m = int(input())
num_list = list(map(int, input().split()))

answer = [0 for _ in range(m)]
card_dict = {}

for i in card_list:
    card_dict[i] = 1

for idx, i in enumerate(num_list):
    if card_dict.get(i) == 1:
        answer[idx] = 1

print(answer)

dictionary 를 만들어 검색하는 방법이다. dictionary 는 리스트와 다르게 검색 시간 복잡도가 O(1)이기 때문에 너무 유용하다. 히히

시간 복잡도 : O(n)

공간 복잡도 : O(n)

 

 

+) 4. set함수 사용하기

인터넷으로 검색을 해보니 단순히 list 대신 set 함수를 사용하면 되는 것이어따...!!!

그리고 까먹고 있었던 in 함수를 사용하면 굉장히 간단한 코드가 완성되는 것이었다.

 

dictionary와 set은 순서와 인덱스 없이 구성되므로 모든 원소를 순회할 필요가 없기 때문에

list 의 검색 시간 복잡도 : O(n)

dictionary 와 set 의 검색 시간 복잡도 : O(1)

가 나오게 된다.

n = int(input())
card_list = set(map(int, input().split()))
m = int(input())
num_list = list(map(int, input().split()))

answer = [0 for _ in range(m)]

for idx, i in enumerate(num_list):
    if i in card_list:
        answer[idx] = 1

print(answer)

 

! 위 모든 코드는 백준 문제와는 출력 형식이 다름