[백준_python] 숫자 카드 1, 2 || 10815, 10816

www.acmicpc.net/problem/10815

10815번: 숫자 카드

기존에 가지고 있던 카드라면 1, 아니라면 0을 출력하는 문제이다.
내가 맨 처음 이분 탐색을 이용해주었던 문제라서 다른 분들 코드를 보며 참고했던 기억이 난다.
또 다른 이분 탐색 문제로는,
전에 풀었던 수 찾기(1920) www.acmicpc.net/problem/1920
[백준_python] 이분 탐색 - 수 찾기 || 1920 :: coding 공부 ~^~^ (tistory.com)
가 생각나는 군..
 

#숫자 카드 (시간초과)

n = int(input())
arr = list(map(int, input().split(' ')))

m = int(input())
arr2 = list(map(int, input().split(' ')))

for i in range(m):
    if arr2[i] in arr:
        arr2[i] = 1
    else:
        arr2[i] = 0

print(*arr2, end = "")

list의 in연산의 시간 복잡도가 O(N)이라서 그런지 시간 초과

#숫자카드_2 (이분 탐색으로 시간 초과 해결)

n = int(input())
arr = list(map(int, input().split(' ')))
arr.sort()
m = int(input())
arr2 = list(map(int, input().split(' ')))

result = []
for i in arr2:
    left = 0
    right = n-1
    while (left <= right):
        mid = (left+right)//2
        if i < arr[mid]:
            right = mid - 1
        elif i > arr[mid]:
            left = mid + 1
        elif i == arr[mid]:
            result.append(1)
            break
    if left > right:
        result.append(0)

print(*result, end="")

이분 탐색을 이용하여 시간 복잡도 O(logN)이 되며 시간 초과를 해결하였다.

---

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

가지고 있는 카드라면 가진 수만큼, 없다면 0 출력
알고리즘에 이분 탐색이라고 적혀있는 것을 보고 아.. 이거도 시간 초과를 보겠구나 싶었다.!

#숫자 카드 2 (시간 초과)
import sys
n = int(sys.stdin.readline())
arr1 = list(map(int, input().split(' ')))

m = int(sys.stdin.readline())
arr2 = list(map(int, input().split(' ')))
result = []
for i in arr2:
    result.append(arr1.count(i))

print(*result, end = " ")

일단 10815 문제처럼 그대로 내 생각대로 굳이 이분 탐색을 사용하지 않아주고 풀어줘보았다. 
아 혹시나 input을 sys로 사용하여 입력 받아준다면 시간이 좀 줄어드나 싶어서 해줘봤지만 역시 시간 초과!
 
그래서 이분 탐색을 써주냐라고 생각이 들겠지만
나는 숫자의 개수를 보는 순간 그냥 Counter가 떠올랐다. ㅎㅎㅎ 왜냐 알고리즘 분류에 자료 구조, 이분 탐색, 해시를 사용한 집합과 맵 이라고 적혀있었다.
 
해시?? 해시???하면 dictionary아닌가라고 생각이 들어서 Counter함수를 이용해줘보았다!

#숫자 카드 2_2 (해시 테이블로 시간 초과 해결)

import sys
from collections import Counter

n = int(sys.stdin.readline().strip())
arr1 = list(map(int, sys.stdin.readline().split(' ')))
arr1 = Counter(arr1)

m = int(sys.stdin.readline().strip())
arr2 = list(map(int, sys.stdin.readline().split(' ')))
result = []

for i in arr2:
    print(arr1[i], end=" ")
    

# for i in arr2:
#     if i in arr1:
#         print(arr1[i], end=" ")
#     else:
#         print(0, end=" ")


#? print(' '.join(f'{arr1[i]}' if i in arr2 else 0 for i in arr2))

너무 비슷한 코드이지만,,! Counter를 이용해주므로 시간 복잡도가.. 아마 다른 것보다는 줄어들어서 시간 초과가 되지 않는다..ㅎㅎ
 
그리고 맨 마지막 한 줄로 간략하게 정리할 수 있는 포맷팅이 있는데 아직 저 포맷팅은 서툴러서 기존 나의 방식대로 출력해주었다..ㅠ..