백준 10815번 파이썬 풀이: 숫자 카드

백준 10815번 숫자 카드

 

알고리즘 분류: 이분 탐색, 정렬

 

링크: www.acmicpc.net/problem/10815

 

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을 공백으로 구분해 출력한다.

 

 

문제 파악

 

이 문제는 주어지는 입력 값이 엄청 크기 때문에 if in 문법을 통해서 찾는다면 무조건 시간 초과가 날 것이다.

 

그럼으로 알고리즘 분류가 이분 탐색으로 되있다는게 힌트라고 할 수 있다.

 

주어지는 입력 값들이 상근이가 가지고 있는 숫자 카드라면 1을 리턴하고 그렇지 않으면 0을 리턴해서

 

공백으로 구분되는 문자열을 출력하는 문제이다.

 

문제 자체는 간단하기 때문에 이분 탐색 알고리즘을 푸는 방법을 알고 있다면 쉽게 풀 수 있을 것이다.

 

 

코드

# 10815번

import sys

def binary_search(element, some_list, start=0, end=None):
    if end == None:
        end = len(some_list) - 1
    if start > end:
        return 0

    mid = (start + end) // 2

    if element == some_list[mid]:
        return 1
    elif element < some_list[mid]:
        end = mid - 1
    elif element > some_list[mid]:
        start = mid + 1
    
    return binary_search(element, some_list, start, end)


n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

sorted_list = sorted(n_list)

answer_list = []

for i in range(len(m_list)):
    answer_list.append(binary_search(m_list[i], sorted_list))

answer = " ".join(map(str, answer_list))
print(answer)

binary_search 함수에 대한 설명은 앞서 풀었던 문제에서 설명이 되어있다.

 

중요한건 지금 만들어져있는 이분 탐색 함수는 리스트가 오름차순으로 정렬되어있는

 

리스트에서만 작동하도록 설계가 되어있다.

 

따라서 상근이가 가지고 있는 리스트를 오름차순으로 정렬해서 이분 탐색 해주면 된다.

 

answer_list 라는 빈 리스트를 만들어서 리턴값들을 append해주는 식으로 풀었다.

 

중요한건 이런식으로 풀면 답이 나오기는 하지만 시간을 꽤 많이 쓰게 된다.

 

어떤 분이 코드길이도 훨씬 짧고 시간도 적게 들었길래 어떻게 풀었는지 소스를 찾아보았는데

 

이 분은 이분 탐색으로 풀지 않고 딕셔너리를 이용해서 풀었다.

 

# 10815번

import sys

n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

dict1 = {m_list[i]: 0 for i in range(len(m_list))}

for i in range(n):
    if n_list[i] in dict1.keys():
        dict1[n_list[i]] += 1
print(" ".join(map(str, list(dict1.values()))))

알고리즘 분류는 이분 탐색으로 되어있으나 문제에서 꼭 그렇게 풀으라고 하지는 않았기 때문에

 

이 방식이 더 빠르고 편하다면 딕셔너리를 이용해서 푸는것도 좋은 해결법이 될 수 있다.

 

파이썬에서 딕셔너리를 이용하면 리스트만 이용해서 푸는 것 보다 시간복잡도를 많이 줄일 수 있다.

 

딕셔너리에 m_list의 길이만큼 m_list의 인덱스를 key로 놓고 value를 0으로 초기화해둔다.

 

반복문을 도는 동안 상근이가 가지고 있는 숫자 카드가 딕셔너리의 key 중에 존재한다면

 

그 key의 value값을 +1 해준다.

 

마지막으로 딕셔너리의 value값들을 리스트로 바꿔주고 안에 요소들을 문자열로 바꿔준다음에

 

공백으로 구분되는 문자열로 출력해주면 된다.

 

아래가 딕셔너리를 통해서 풀은 코드이고 위에가 이분 탐색을 통해서 풀은 코드이다.

 

딕셔너리를 통해서 풀은 코드가 코드 길이도 짧고 시간도 적게 소모되는 것을 볼 수 있다.

 

이분 탐색으로 처음에 정답을 맞았을 때 시간이 꽤 많이 소모되었길래

 

처음엔 input을 사용해서 그런가 생각했는데 sys.stdin.readline을 사용하여도

 

4428 ms -> 4220 ms 로 크게 유의미한 차이는 보이지 못했다.