[백준 Python] 10815번 숫자 카드 파이썬 풀이

단계별로 풀어보기 - [집합과 맵] - 10815번 숫자 카드

문제

---

문제링크

 

 

풀이

---

1차 시도_ 실패

이게 왜 집합과 맵 단계지 하고 그냥 풀었는데

n = int(input())
nums = [int(n) for n in input().split()]
m = int(input())
cards = [int(n) for n in input().split()]

for i in cards:
    if i in nums:
        print(1, end=' ')
    else:
        print(0, end=' ')

가차없이 시간 초과..ㅎ

 

2차 시도_ 성공

혹시 input함수 때문인가 싶어서 input 대신 sys.stdin.readline 함수로 바꾸고,

리스트 대신 set으로 만들었더니 통과되었다.

 

set에 저장하면 출력했을 때 자동으로 정렬되어 있는 것을 확인할 수 있다.

상근이가 가지고 있는지 검사해야 하는 카드들은 입력된 데이터 순서대로 검사해서 있는지 없는지 알려줘야 하기 때문에 리스트로 받았다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
nums = set(int(n) for n in input().split())

m = int(input())
cards = [int(n) for n in input().split()]

for i in cards:
    if i in nums:
        print(1, end=' ')
    else:
        print(0, end=' ')

결과

---

 

---

다른 풀이1) dictionay 이용

다른 사람들은 어떻게 풀었나 찾아봤더니, dictionary를 사용한 풀이가 많았다.

dictionary의 key에는 검색할 숫자, value에는 상근이에게 카드가 있으면 1, 없으면 0을 넣는다.

그러면 해당 카드가 있는지 없는지 모든 원소를 일일이 확인하지 않아도 되기 때문에 속도가 더 빨라진다.

여기서는 input()함수를 그대로 사용했음에도 통과할 수 있었다.

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

dic = {}

for c in cards:
    dic[c] = 0

for i in nums:
    if i in dic:
        dic[i] = 1

for d in dic:
    print(dic[d], end=' ')

 

 

다른 풀이2) 이진 탐색

그리고 이진 탐색을 통해서도 빠르게 찾을 수 있다고 한다.

import sys
input = sys.stdin.readline

n = int(input())
cards = sorted(list(map(int, sys.stdin.readline().split())))
m = int(input())
checks = [int(n) for n in input().split()]

for check in checks:
    low, high = 0, n-1  # cards의 이진 탐색 index
    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
    print(1 if exist else 0, end=' ')