[백준/Python] 10815번 : 숫자 카드

10815번: 숫자 카드

시간 제한	메모리 제한	문제 티어	정답 비율
2 초	256 MB	실버 V	44.135%

📜 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

 

💡풀이

풀이하기 전, 우리는 다음의 개념과 원리를 알아야 한다.

 

● 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

● 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법(시작점, 끝점, 중간점을 활용하여 탐색 범위를 설정)

 

순차탐색으로 풀이하면 아래 코드와 같다.

import sys

input = sys.stdin.readline

N = int(input())

your_card = list(map(int, input().rstrip().split()))

M = int(input())

compare_card = list(map(int, input().rstrip().split()))

for num in compare_card:
  if num in your_card:
    print(1, end=" ")
  else:
    print(0, end=" ")

그러나 이 경우, 시간복잡도는 O(n)이고 시간초과가 된다. 따라서 우리는 시간복잡도가 O(log N)인 이진탐색을 사용하여야 한다.

이진 탐색의 경우, 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log_2(N)에 비례한다. 예를 들어 데이터의 개수가 64개일 때, 이상적으로 이진 탐색의 1단계를 거치면 32개 데이터만 남고, 2단계를 거치면 16개, 3단계는 8개... 이런 식으로 이진 탐색의 범위를 절반씩 줄인다.

따라서 이진 탐색의 시간 복잡도는 O(log N)이다.(시간 복잡도는 상수는 없는거나 마찬가지이므로)

내가 이진 탐색으로 풀이한 두 가지 방법은 아래와 같다.

1) 재귀 함수를 이용

import sys

def binary_search(array, check, start, end):
  if start > end:
    return False
  mid = (start + end) // 2
  if check == array[mid]:
    return True
  elif check > array[mid]:
    start = mid + 1
    return binary_search(array, check, start, end)
  else:
    end = mid - 1
    return binary_search(array, check, start, end)

input = sys.stdin.readline

N = int(input())
your_card = sorted(list(map(int, input().rstrip().split())))

M = int(input())
compare_card = list(map(int, input().rstrip().split()))

for num in compare_card:
  if binary_search(your_card, num, 0, N-1):
    print(1, end=' ')
  else:
    print(0, end=' ')

 

2) while문을 이용

import sys

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

input = sys.stdin.readline

N = int(input())
your_card = sorted(list(map(int, input().rstrip().split())))

M = int(input())
compare_card = list(map(int, input().rstrip().split()))

for num in compare_card:
  if binary_search(your_card, num, 0, N-1):
    print(1, end=' ')
  else:
    print(0, end=' ')

 

사실 파이썬은 세트 함수나 딕셔너리 함수의 연산시간이 상수라서, 이 방법을 사용하는 것도 한 가지 방법이지만, 우리는 알고리즘을 배우므로 이진 탐색을 어떻게 구현하는지에 대해 배워보았다.

추후 시간이 나면 딕셔너리로 풀이하는 방법도 수정해서 올리겠다.