[백준 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보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 N개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

초기 코드

N = int(input())	# 첫째 줄
my = list(map(int, input().split()))	# 둘째 줄

M = int(input())	#셋째 줄

card = list(map(int, input().split()))	# 넷째 줄

inter = set(my) & set(card)

for x in card:
    if x in inter:
        card[card.index(x)] = 1
    else:
        card[card.index(x)] = 0

for x in card:
    print(x, end = ' ')

의식의 흐름

1. 일단 입력을 리스트로 받자

2. 집합으로 바꾼 후 둘째 줄과 넷째 줄의 교집합을 구하면 1을 출력할 숫자 목록이 나온다. -> 리스트로 바꿔준다

3. for문으로 요소를 하나씩 훑으면서 1과 0으로 바꿔준다.

4. 결과: 시간 초과

문제점: for문으로 요소 하나씩 훑게 되면 N이 백만일 경우 백만개 훑어야 하니까? 시간 단축해야해

=> 순차 탐색을 사용하면 안되는구나

다른 탐색 방법 여러가지 있는데 내가 아는건 이진 탐색밖에 없어...(코드 짜본적도 없긴 한데 기억나는게 저거밖에 없다)

한번 써보자

이진 탐색

순차 탐색은 왼쪽부터 하나씩 보면서 탐색하는, 즉 시간이 굉장히 오래 걸린다. 

이진 탐색은 정렬된 자료를 가운데를 기준으로 계속 절반으로 나눠서 (왼쪽 오른쪽, 그 왼쪽의 중심의 왼쪽 오른쪽 ...) 원하는 답을 찾을 때까지 탐색

처음부터 절반만 보니까 당연히 시간이 덜 걸린다.

수정 코드

N = int(input())
my = list(map(int, input().split()))
M = int(input())
card = list(map(int, input().split()))

my.sort()

for x in card:
    answer = 0
    start = 0
    end = len(my) - 1 # 인덱스니까 -1 해줘
    
    while start <= end:
        mid = (start + end) // 2
        if my[mid] == x:
            answer = 1
            break
        elif my[mid] < x:
            start = mid + 1
        else:
            end = mid - 1
    print(answer, end = " ")

간단한 설명

1. 입출력은 동일하게 받아온다.

2. 이진 탐색을 위해 my나 card를 정렬해줘야 하는데, card를 기준으로 정답을 출력해야 하므로 my를 sort로 정렬해준다.

3. for문으로 시작해서 card의 요소들을 하나하나 불러온다.

4. start, end index를 설정해주고, while 문으로 start == end가 될 때까지 반복시킨다.

4. x가 my에 존재하는지 탐색하고, 없으면 start와 end index를 재설정한다.

5. 끝