백준(baekjoon) 10815번: 숫자 카드(실버 5, 파이썬 PYTHON) - 집합과 맵

문제

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

 

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

10815번: 숫자 카드

 

import sys

N=int(sys.stdin.readline())
num_list=list(map(int,sys.stdin.readline().split()))
M=int(sys.stdin.readline())
check_list=list(map(int,sys.stdin.readline().split()))
check_result=[]

num_list.sort() 

def bin_search(num,start,end):  
  global num_list
  if(start>end): 
    return False  
  else: 
    mid=(start+end)//2  
    if(num_list[mid]==num): 
      return True 
    if(num_list[mid]>num): 
      return bin_search(num,start,mid-1) 
    if(num_list[mid]<num): 
      return bin_search(num,mid+1,end) 
    
for x in check_list:  
  result=bin_search(x,0,N-1)  
  if(result==True): 
    check_result.append(1) 
  elif(result==False):
    check_result.append(0) 

print(*check_result)

 

※ 집합과 맵

 

 

시간초과를 방지하기 위해 이진 탐색을 이용하여 문제를 해결한다.

 

● 먼저 가지고 있는 숫자카드의 숫자를 num_list 배열에 저장한 후, sort() 함수를 통해 오름차순 정렬한다.

 

● 그 후 존재 유무를 확인해야 할 숫자들을 check_list 배열에 저장한다.

 

● 모든 check_list안의 요소들에 대해 bin_search() 라는 함수를 정의하여 이진탐색을 진행한다. 이 때 처음 bin_search를 진행하는 범위는 num_list 배열의 처음부터 끝까지이다.

bin_search() 는 현재 찾아야 할 수, 탐색해야하는 배열 범위의 첫 인덱스와 마지막 인덱스를 매개변수로 갖는다.

 

● 탐색해야 하는 배열 범위의 첫 인덱스가 마지막 인덱스보다 큰 값을 가지게 되면 그때까지 찾아야 하는 수를 못 찾은 것이므로 False를 return 해준다.

 

● 탐색해야 하는 배열 범위의 첫 인덱스가 마지막 인덱스보다 작거나 같은 값을 가지면 탐색해야 하는 배열 범위의 중간 인덱스를 mid 변수에 저장한다.

 

● 그 후 mid 값을 인덱스로 하는 요소의 값이 현재 찾아야 할 수와 같으면 그 수를 찾은 것이므로 True를 return 해준다.

 

● 만약 mid 값을 인덱스로 하는 요소의 값이 현재 찾아야 할 수보다 크면, 배열 인덱스의 범위를 현재 배열 범위의 처음부터 mid 값을 인덱스로 하는 요소 바로 전까지 다시 탐색하도록 범위를 설정하여 bin_search() 함수를 호출해준다.

 

● 또한 mid 값을 인덱스로 하는 요소의 값이 현재 찾아야 할 수보다 작으면, 배열 인덱스의 범위를 mid 값을 인덱스로 하는 요소 바로 다음 요소부터 현재 배열 범위의 끝까지 다시 탐색하도록 범위를 설정하여 bin_search() 함수를 호출해준다.

 

● 그 후, 탐색을 수행한 값이 True가 나오면 check_result 라는 배열에 1을 append, False가 나오면 0을 append 해준 뒤, check_result 배열을 출력해주면 된다!!

 

 

결과

 

 

♣ 참고: 이진탐색

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이진 탐색 - 나무위키