백준 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을 공백으로 구분해 출력한다.
이진탐색(binary search)은 코딩 테스트 단골 문제다. 대체로 쉬운 문제로도 분류된다. 초보인 내겐 다르다. 이 유형의 문제를 많이 못 푼 탓에, 여전히 어렵게 느껴진다. 방법은 하나다. 반복 학습으로 익숙해지는 수밖에.
이번 문제도 관건은 시간 초과를 피하는 일이었다. 십여 차례 시도 끝에 겨우 통과했다.
이진탐색 함수를 만들어두고 대입하는 식으로 풀었는데, 시간 초과가 났다. 원인은 함수 안에 넣어둔 리스트 정렬 메소드(sort())였다. 함수가 돌 때마다 정렬을 반복하니 시간 초과가 날 수밖에.
처음 푼 코드.
import sys
input = sys.stdin.readline
def bin_search(target, data):
data.sort() # 함수가 실행할 때마다 데이터를 정렬한다.
start = 0
end = len(data) - 1
while start <= end:
mid = (start + end) // 2
if data[mid] == target:
return 1
elif data[mid] < target:
start = mid + 1
elif data[mid] > target:
end = mid - 1
return 0
n = int(input())
mycard = list(map(int, input().split()))
m = int(input())
addcard = list(map(int, input().split()))
for i in addcard:
res = bin_search(i, mycard)
print(res, end=' ')
수정한 코드. 통과!
import sys
input = sys.stdin.readline
def bin_search(target, data):
start = 0
end = len(data) - 1
while start <= end:
mid = (start + end) // 2
if data[mid] == target:
return 1
elif data[mid] < target:
start = mid + 1
elif data[mid] > target:
end = mid - 1
return 0
n = int(input())
mycard = sorted(list(map(int, input().split()))) # 리스트를 만들 때 데이터를 정렬해준다.
m = int(input())
addcard = list(map(int, input().split()))
for i in addcard:
res = bin_search(i, mycard)
print(res, end=' ')
인생은 짧다. 뛰자!
[문제 보기]