[Python] 백준 10815 숫자 카드

 

문제 분석

• 정수 1개가 적혀있는 카드
• 숫자 카드를 N개 가지고 있음
• 정수 M개가 주어졌을 때 이 수가 적혀있는 숫자 카드를 가지고 있는지 구하라
• 각 수에 대해 (M) 가지고 있으면 1, 아니면 0 출력

 

정답 코드

1차 - 실패 (시간초과)

import sys
input = sys.stdin.readline

n = int(input())
have_card = sorted(list(map(int, input().split())))
m = int(input())
check = list(map(int, input().split())) # check를 정렬하면 출력되는 순서도 달라져서 정렬하면 x

for c in check :
    if c in have_card :
        print(1, end=' ')
        have_card.remove(c)
        continue
    else :
        print(0, end=' ')
        continue

• M(1 ≤ M ≤ 500,000), N(1 ≤ N ≤ 500,000)
• 숫자 하나당 in으로 검사하면 총 500,000 x 500,000 연산횟수 필요
• 즉, 250,000,000,000 (2,500억 횟수 필요)
• 1초에 1억이라고 했을 때, 당연히 시간 초과..
• 이중 반복문은 시간초과..

실패..

 

다른 사람 코드 1 - dictionary (속도는 딕셔너리!)

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
check = list(map(int, input().split()))

dict = {}
for i in range(n) :
    dict[cards[i]] = 0

for j in range(m) :
    if check[j] in dict :
        print(1, end = ' ')
    else :
        print(0, end = ' ')

 

다른 사람 코드 2 - 이진 탐색

1. 가지고 있는 cards를 sort 시킨다.
2. 체크할 배열 checks에서 check를 하나씩 꺼내면서
3. 이진 탐색을 위한 low, high, mid를 지정
4. cards의 중간 index와 비교한다.
5. check가 중간 값보다 작다면, 왼쪽 한 칸 옆까지 탐색하게 high를 조정
6. check가 중간 값보다 크다면, 오른쪽 한 칸 옆부터 탐색하게 low를 조정
7. check가 중간 값과 일치하면 바로 멈추고 1 출력
8. 끝까지 없다면 (exist = 그대로 False) 0 출력

import sys
input = sys.stdin.readline

n = int(input())
cards = sorted(list(map(int, input().split())))
m = int(input())
checks = list(map(int, input().split()))

for check in checks :
    low, high = 0, n-1
    exist = False
    while low <= high :
        mid = (low + high) // 2
        if cards[mid] > check : # 중간값 보다 작으면
            high = mid-1 # 중간보다 왼쪽 한칸 옆까지 탐색
        elif cards[mid] < check : # 중간값 보다 크면
            low = mid + 1
        else :
            exist = True # 있으면
            break
    # card에 대해 탐색 끝
    print(1 if exist else 0, end = ' ')