[BOJ][Python] 10815번 - 숫자카드[정렬- 실버 4티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 숫자카드

링크: 숫자카드

문제설명

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

단순한 문제다. 말 그대로 상근이가 가지고 있는 카드가 정수에 있는지 없는지를 판단해서 결과값을 내어주면된다.

 

예제 입력 

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

예제 출력 

1 0 0 1 1 0 0 1

📃 소스코드 및 설명

# 상근이가 가지고 있는 카드수
N = int(input())

# set을 사용하여 같은 수가 들어와서 중복될 경우,
# 순차탐색은 시간초과가 날 수 있으므로, 중복을 제거해준다.
N_list = set(map(int,input().split()))

# 주어지는 정수 갯수
M = int(input())
M_list = list(map(int,input().split()))

result = []

for card in M_list:
  if card in N_list:
    result.append(1)
  else:
    result.append(0)
    
print(*result)

이 방법도 있지만, 숫자목록이 많아질 경우 시간초과를 방지하기 위해서 이진탐색을 사용하여 처리하는 방식도 있다.

 

이진탐색이란?

데이터가 정렬되 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

📃 소스코드 및 설명

# 상근이가 가지고 있는 카드수
# N = int(input())

#[6, 3, 2, 10, -10]
N_list = list(map(int,input().split()))

# 정렬
# [-10, 2, 3, 6, 10]
N_list.sort()

# 주어지는 정수 갯수
M = int(input())

# [10, 9, -5, 2, 3, 4, 5, -10]
M_list = list(map(int,input().split()))

def binary_search(array, target, start, end):
  """  
  parameter
          array : 상근이가 가지고 있는 카드
          target : 주어진 정수에서 찾고자 하는 카드
          start : 0(리스트 인덱스)
          end : 상근이가 가지고 있는 카드의 길이의 끝점 인덱스   
  """
  # 시작포인트가 end보다 커지면 break
  # 즉 중간 지점을 기준으로 좌, 우로 움직이다 끝점이 start점보다 작아지는 경우 break을
  # 하게된다.
  while start <= end:
    # 두 숫자를 더해서 중간을 구하기 위해 몫을 구한다.
    mid = (start + end)//2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      # 만약 중간값보다 배열의 값이 크다면 좌측으로 옮긴다.
      end = mid - 1
    else: 
      # array[mid] < target
      # 만약 중간값보다 배열의 값이 작다면 우측으로 옮긴다.
      start = mid + 1 
  return None
      
for i in range(M):
  # N_list의 요소들값을 기준으로해서 좌, 우로 움직여가며 탐색을 진행한다.
  # start, end는 아래와 같이 리스트의 처음부터 끝까지로 정해서 시작한다.
  result = binary_search(N_list, M_list[i], 0, N - 1)
  if result is not None:
    print(1, end=' ')
  else:
    print(0, end=' ')