숫자 카드
출처 | 숫자카드 [백준 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을 공백으로 구분해 출력한다.
풀이
처음에는
from sys import stdin
N = int(input())
user_card = list(map(int, stdin.readline().split()))
M = int(input())
check_card = list(map(int, stdin.readline().split()))
result = ""
for i in check_card:
if i in user_card:
result += "1 "
else:
result += "0 "
print(result)
이런 식으로 ‘if in list‘를 사용하여 접근했지만 시간초과로 해결하지 못 했다.
그 이유는 ‘if in list’를 사용할 경우 모든 값을 순회하므로 O(n)의 시간복잡도가 발생하고 결과적으로 O(n^2) 의 시간복잡도를 가지게 되기 때문이었다.
# 이분탐색
from sys import stdin
N = int(input())
user_card = list(map(int, stdin.readline().split()))
user_card.sort()
user_card.insert(0, 0)
M = int(input())
check_card = list(map(int, stdin.readline().split()))
def binary_search(start, end, num, array):
while start <= end:
mid = (start + end) // 2
if array[mid] < num:
start = mid + 1
else:
end = mid - 1
if user_card[start] == num:
return "1 "
return "0 "
result = ""
for n in check_card:
result += binary_search(1, N-1, n, user_card)
print(result)
그 후 이분탐색을 이용하여 문제를 접근했고, 문제는 해결했지만 다른 사람들의 풀이법과 비교했을 때 느린 편에 속하는 풀이법이었다.
from sys import stdin
N = int(input())
user_card = set(map(int, stdin.readline().split()))
M = int(input())
check_card = list(map(int, stdin.readline().split()))
def solution():
result = ""
for i in check_card:
if i in user_card:
result += "1 "
else:
result += "0 "
return result
print(solution())
검색을 통해 python에서 set가 해시 테이블로 구현되어 있기 때문에 ‘if in set’의 시간복잡도는 O(1)이 될 수 있다는 것을 알게 되었다. 간단하게 해시 테이블에 대해 설명하자면
해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조라고 한다. 이때 연관배열 구조(associative array)란 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다. 이때 검색의 경우 1) 키로 hash를 구한다. 2) hash로 값(value)를 찾는다. 라는 과정을 수행하므로 대부분의 경우 시간복잡도 O(1)을 가지게 된다.
출처_위키백과
출처
알고리즘 분류
Reference
