[백준] 10816번 숫자 카드 2

❓문제

[실버4]
https://www.acmicpc.net/problem/10816

💭 아이디어

숫자 카드에 적혀있는 수의 범위가 매우 크므로 이진탐색을 자연스럽게 떠올렸다.
이진탐색을 하기 위해 상근이가 가지고 있는 숫자카드 배열에 대해 정렬을 해주어야 한다.

이 문제는 찾고자 하는 숫자가 범위 내에 있는지 없는지 '유무'를 따지는 것에 덧붙여 있다면 몇개인지까지 구해야 한다.
이를 위해 상근이가 가지고 있는 숫자카드를 입력받고, 이 배열을 순회하며 딕셔너리에 하나의 숫자가 몇개 있는지 기록한다.
예를 들어 6 3 2 10 10 10 -10 -10 7 3 를 입력하면,
{-10: 2, 2: 1, 3: 2, 6: 1, 7: 1, 10: 3}
이런 식으로 각 숫자가 배열에 몇개 존재하는지 딕셔너리에 저장하는 것이다.

따라서 찾고자 하는 숫자가 범위 내에 있다면, 딕셔너리에서 그 값이 몇개 있는지 찾으면 된다.
없을 경우 당연히 찾는 과정은 pass

❗ 풀이

import sys

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

m = int(input())
array = list(map(int, sys.stdin.readline().split()))

n = int(input())
x = list(map(int, sys.stdin.readline().split()))

array.sort() # 이진탐색을 위해 sort

# 원소의 개수를 저장하는 딕셔너리
arrayNum = {}
for i in array:
    if i in arrayNum.keys():
        arrayNum[i] += 1
    else:
        arrayNum[i] = 1
# print(arrayNum)

answer = [] # 숫자카드의 개수
total = 0
for i in range(n):
    result = binary_search(array, x[i], 0, m-1-total)
    if result == None:
        answer.append(0)
    else:
        answer.append(arrayNum[x[i]]) # 가지고 있을 경우 딕셔너리에서 그 숫가가 몇개인지 찾기
            
for i in range(n):
    print(answer[i], end = " ")

[딕셔너리에 원소 개수를 기록할 때]
이미 해당 원소가 딕셔너리의 키 값으로 있다면 value 값을 1 증가시키기
없다면 1로 딕셔너리에 새로 추가하기

✅ Comment

이진탐색 문제는 이제 몇개 풀어봐서 충분히 구현 가능했으나 찾고자 하는 숫자가 범위 내 한개가 아닌, 두개 이상일 때 어떻게 찾아야 되는지 감이 잡히지 않았다.
왼쪽 배열 탐색 ? 오른쪽 배열 탐색 ? 그런데 현재 찾은 값의 인덱스인 mid가 10 10 10 이렇게 세개 중 두번째를 가르킨 것이라면 .. 등등 고민이 많았고 결국 생각해낸 것은 값을 찾으면, 배열에서 pop 시키고 다시 이분탐색을 진행하는 것이었다. 그러면 그 값이 없을 때까지 이분탐색을 진행하게 될테니 ... 정말 비효율적이지만 다른 방법이 생각나지 않아 일단 구현을 했고 답 출력은 잘 되었다. 그런데 백준에서 오답이라고 하더라구요 .. 그래서 구글링 시작~! 해서 딕셔너리라는 미친 답안을 접했다. 배열을 순회하며 딕셔너리에 키값으로 원소 값, 벨류값으로 원소의 개수 를 기록하는 .. 이러면 이분탐색에서 찾기만 하면 딕셔너리에서 키값으로 접근해 벨류값이 몇인지만 확인하면 끝.. ! 쏘이지했던 것이다.
주절주절이지만 딕셔너리의 이러한 활용법을 땩 머릿속에 넣어두게 되었다 ..!

이 문제를 구글링하면 다른 풀이도 정말 많으니 한번씩 보는 걸 추천드립니다!

아래는 틀렸던 코드이다..^^..

import sys

def binary_search(array, target, start, end):
    global total
    count = 0
    while start <= end:
        mid = (start + end) // 2
        # print(start, end, mid)
        
        if array[mid] == target:
            count += 1
            total += 1
            array.pop(mid)
            # print(array, count, total)
            start = 0
            end = m - 1 - total
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return count

m = int(input())
array = list(map(int, sys.stdin.readline().split()))

n = int(input())
x = list(map(int, sys.stdin.readline().split()))

array.sort() # 이진탐색을 위해 sort

answer = [] # 숫자카드의 개수
total = 0
for i in range(n):
    result = binary_search(array, x[i], 0, m-1-total)
    if result == 0:
        answer.append(0)
    else:
        answer.append(result)
            
for i in range(n):
    print(answer[i], end = " ")