백준 알고리즘 10815 (숫자 카드) - python

백준 알고리즘 10815 (숫자 카드) - python

> https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

가지고 있는 숫자 카드를 체크하는 것이다.

결론적으로 큰 배열이 있을 때 효율적으로 비교 탐색이 가능한가를 묻는 문제.

dictionary, 이진 탐색의 2가지를 이용해서 풀이했다.

속도는 역시 dictionary! python 최고!

 

[문제 풀이 1 : dictionary]

1. 가지고 있는 cards를 모두 _dict(dictionary)에 0(아무 숫자로 가능)로 등록

2. 체크할 배열 checks가 _dict에 있으면 1, 없으면 0 출력

 

import sys

N = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))

_dict = {}  # 속도는 dictionary!
for i in range(len(cards)):
    _dict[cards[i]] = 0  # 아무 숫자로 mapping

for j in range(M):
    if checks[j] not in _dict:
        print(0, end=' ')
    else:
        print(1, 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

N = int(sys.stdin.readline())
cards = sorted(list(map(int, sys.stdin.readline().split())))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().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=' ')