[백준 10816 파이썬] 숫자 카드 2 (실버4, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : X

https://www.acmicpc.net/problem/10816

SOLVE 1

딕셔너리 이용, 이분 탐색

import sys
input = sys.stdin.readline

N = int(input())
cards = sorted([*map(int, input().split())])
M = int(input())
candidate = [*map(int, input().split())]

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

def binarySearch(arr, target, start, end):
    if start > end:
        return 0
    
    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid+1, end)
    else:
        return binarySearch(arr, target, start, mid-1)
    
for target in candidate:
    print(binarySearch(cards, target, 0, len(cards)-1), end=" ")

SOLVE 2

딕셔너리 이용, 키 조회

import sys
input = sys.stdin.readline

N = int(input())
cards = [*map(int, input().split())]
M = int(input())
candidate = [*map(int, input().split())]

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

for target in candidate:
    result = count.get(target)
    if result == None:
        print(0, end=" ")
    else:
        print(result, end=" ")

리뷰

처음엔 이분 탐색에서, target을 찾았을 때, 그 인덱스로부터 양 옆으로 뻗어나가면서(for) target의 개수를 찾는 코드를 작성했는데 시간 초과가 떴다. 도저히 다른 이분 탐색 응용 방도가 안 떠올라서 다른 사람 풀이를 참고했는데... 이 문제는 이분 탐색으로 풀 이유가 전혀 없는, 단순한 딕셔너리 문제인데... 그래도 꾸역꾸역 이분 탐색 활용 풀이도 작성해봤다.

SOLVE 1) 풀이 요약 (딕셔너리 이용, 이분 탐색)

1. cards에 카드들을 모두 담고, 이를 딕셔너리에 따로 담는다. 키는 카드의 숫자이고, 밸류는 그 카드의 개수이다.

   그리고 이분 탐색을 돌면서 타겟을 찾았을 때, 그 때의 인덱스 mid를 반환하지 않고, mid-1, mid+1부터 왼쪽, 오른쪽으로 쭉 뻗어나가면서 target의 개수를 계산 후 그걸 반환해주면 된다. 그런데, 이럴 필요없이 그냥 만들어놓은 딕셔너리를 target을 키로 인덱싱하면 O(1)로 답을 찾을 수 있다.. 이분 탐색을 끼워넣으면 O(logN) * O(1)이 되어서 더 오래걸린다.

SOLVE 2 풀이 요약 (딕셔너리 이용, 키 조회)

1. cards에 카드들을 모두 담고, 이를 딕셔너리에 따로 담는다. 키는 카드의 숫자이고, 밸류는 그 카드의 개수이다.

   그리고 candidate를 돌면서, target을 키 값으로 딕셔너리를 인덱싱해서 밸류를 뽑아내주면 된다.

배운 점, 어려웠던 점

• 이분 탐색 카테고리에 있는 문제라 이분 탐색 풀이만 계속 생각했다.

  사실 1번 풀이를 생각도 해봤는데, 대충 생각하다보니 딕셔너리 만드는 과정에서 시간 초과가 날 것이라? 생각을 했다. N이 최대 50만이라 for 돌면 50만번이 최대 연산 횟수인데..

  아무튼 뭐 그냥 딕셔너리 문제였다...