[Baekjoon | 백준] 10815번. 숫자 카드 (파이썬/집합과 맵)

문제

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

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

 

예제 출력 1

 

1 0 0 1 1 0 0 1

 

알고리즘 분류

• 자료구조
• 정렬
• 이분 탐색

 

풀이 방식

딱보면 searching(탐색) 문제인 것을 알 수 있고, 입력 제한이 500,000이기 때문에 이중 for문으로 선형탐색을 진행하면 O(N^2)으로 시간초과가 발생할 것이다.

그렇기 때문에 O(N)이나 O(NlogN) 풀이로 풀어야 한다.

 

1번 풀이:  성공

from collections import Counter
N = int(input())
d = list(map(int, input().split()))
M = int(input())
f = list(map(int, input().split()))

dic = Counter(d)
answer = []
for i in f:
    if i in dic:
        answer.append(1)
    else:
        answer.append(0)
print(*answer)

처음으로 생각한 풀이는 딕셔너리 탐색을 사용하는 것으로 딕셔너리에서 탐색은 O(1)의 시간복잡도를 갖기 때문에 O(N)의 for문 안에서 O(1)의 연산을 수행하기 때문에 전체 시간복잡도가 O(N)인 코드이다.

 

 

이분탐색를 사용한 다른 풀이

일반적인 선형탐색은 O(N)이기 때문에 고려할 수 없는 사항이었지만 이분탐색(binary search)를 사용하면 O(logN)의 연산이 가능하기 때문에 총 O(NlogN)의 시간복잡도로 풀 수 있는 풀이이다.

import sys
import bisect
input = sys.stdin.readline

def solution(ordered_list, target):
    index = bisect.bisect_left(ordered_list, target)

    if index < len(ordered_list) and ordered_list[index] == target:
        return 1
    else:
        return 0


N = int(input())
N_list = list(map(int, input().split()))
N_list.sort()

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

for m in M_list:
    print(solution(N_list, m), end=' ')

이분탐색을 진행해야 하는 리스트는 반드시 정렬이 되어있어야 하고 파이썬 내장 sort()함수는 O(NlogN)의 시간복잡도로 정렬을 하기 때문에 무리없이 사용할 수 있다.

 

위 코드는 bisect를 활용하여 이분 탐색을 진행한 것으로 M 리스트를 O(N)으로 돌면서 그 안에서 O(logN)의 연산이 수행되기 때문에 최종적으로 O(NlogN+NlogN) = O(NlogN)의 시간복잡도의 풀이가 된다.