저별이의 초보 코딩

https://www.acmicpc.net/problem/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을 공백으로 구분해 출력한다.

예제입력

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

예제출력

1 0 0 1 1 0 0 1

코드 및 설명

import sys
input=sys.stdin.readline
n=int(input())
card=list(map(int,input().split()))
m=int(input())
card2=list(map(int,input().split()))
card.sort()
#이분탐색 시작
def search(target,line, st, ed):
    if st>ed:
        return 0
    mid=(st+ed)//2
    if line[mid]>target:
        ed=mid-1
        return search(target,line,st,ed)
    elif line[mid]<target:
        st=mid+1
        return search(target,line,st,ed)
    else:
        return 1
    return 0

num_card=[]
for i in card2:
    start=0
    end=n-1
    re=search(i,card, start,end)
    num_card.append(re)
for i in range(m):
    print(num_card[i],end=" ")

이 문제는 이분탐색으로 풀 수 있는 문제이다.

그래서 '이분탐색'이라는 개념을 알아야 풀기 수월하다.

일단 간단하게 '이분탐색' 개념을 알아보자

이분탐색은 오름차순으로 정렬된 리스트에서 탐색 범위를 절반씩 좁혀나가면서 데이터를 탐색하는 방법이다.

그래서 정렬된 리스트에 중간지점을 지정하고 목표 숫자와 비교해나가면서 탐색범위를 조절한다.

코드도 이를 반영해 보여준다.

주어진 리스트와 크기 정보들은 기본 입출력 부분이기에 설명을 생략한다.

함수를 호출하고 이에 대한 함수만 설명하려고 한다.

일단 특정한 숫자를 호출하기 위해서는 탐색할 범위를 지정해주어야 한다.

그래서 start와 end라는 변수를 통해 처음과 끝을 선언해주고 이를 바탕으로 함수를 호출한다. 

여기서 re는 함수가 리턴되었을 때 받은 숫자를 저장하려고 사용하였다.

그리고 이를 마지막 출력을 위해 리스트에 추가해주었다.

이분탐색을 위해 생성한 함수를 설명해보자면 일단 기준점, 즉 start 부분이 end를 넘어가게 되면 에러가 나고 더이상 숫자를 찾을 수 없는 것을 의미하기에 0을 리턴하게 하였다.

그리고 중간 위치는 start와 end를 더해 1/2로 나누어주면 찾을 수 있기에 매번 이를 활용하도록 하였다.

조건문을 이용하였는데 찾고자하는 숫자보다 중간지점이 크다면 중간지점보다 작은 범위에 있다는 것을 의미한다.

그래서 end부분을 중간지점-1로 설정해 주었다. 이 경우에는 시작점은 변화가 없다.

이 위치를 바탕으로 다시 함수 호출해서 숫자를 탐색한다.

찾고자하는 숫자보다 중간지점이 작다면 어떻게 될까??

그러면 중간지점보다 큰 범위에 있다는 것을 의미하게 된다. 그렇기 때문에 시작지점을 변경해주어야 한다.

start 부분을 중간지점+1로 설정한다. 반대로 이 경우에는 끝지점이 변화가 없게 된다.

여기에서도 역시 다시 함수 호출해서 숫자를 탐색한다.

만약 찾고자 하는 숫자와 중간지점이 같다면,

그대로 return 값을 1로 설정해주면 된다.

이렇게 이분탐색을 진행하면된다.

이분탐색이 개념만 볼 때에는 굉장히 쉬워보이지만 코드를 짤 때는 조금 어렵게 느껴지는 개념이라고 생각한다.

이분탐색을 활용해 문제를 푸는 연습을 많이 해봐야 좀 더 쉽게 접근할 수 있을 것 같다.