백준 숫자 카드2

문제

백준 숫자 카드2 문제 링크

나의 풀이

1. 주어진 숫자 리스트의 중복 숫자 개수를 구하는 문제이기 때문에 어떻게 범위를 찾을 수 있을지 고민한 결과 이분 탐색을 활용하는 방법을 먼저 생각했다.
2. 이분 탐색은 값이 존재하는지 유무를 판단하는데 사용하므로 범위를 알기 위해 upper bound, lower bound를 찾는 코드를 구현해 중복 숫자의 범위를 판단했다.

def lower_bound(arr, target):
    cur_min = 0
    cur_max = len(arr)

    while cur_min < cur_max:
        mid = (cur_min + cur_max) // 2
        if target <= arr[mid]:
            cur_max = mid
        else:
            cur_min = mid + 1

    return cur_min


def upper_bound(arr, target):
    cur_min = 0
    cur_max = len(arr)

    while cur_min < cur_max:
        mid = (cur_min + cur_max) // 2
        if target < arr[mid]:
            cur_max = mid
        else:
            cur_min = mid + 1

    return cur_min

3. 문제 해결 후 python에서 라이브러리를 제공하는 것을 생각한 후 bisect를 사용해 코드를 간소화 했다.

from bisect import bisect_left,bisect_right

...

for i in range(m):
    result.append(bisect_right(cards_num, find_num[i]) - bisect_left(cards_num, find_num[i]))

4. 다른 방법이 있을까 고민하는 중 나온 숫자를 count하는 방식은 속도가 얼마나 걸릴지 궁금하여 dictionary를 사용해 숫자를 count하여 저장하고 결과값을 print하는 방법을 사용했더니 속도가 더 빠른 것을 확인했다.

for num in cards_num:
    if num in dicts:
        dicts[num] += 1
    else:
        dicts[num] = 1

5. Counter 라이브러리를 사용해 문제를 해결한 결과 dictionary를 사용한 방법과 속도가 비슷하여 확인한 결과 Counter가 dictionary를 사용한 방법이었다.

from collections import Counter

...

cnt = Counter(cards_num)

코드

1. upper bound, lower bound를 사용한 풀이

n = int(input())
cards_num = list(map(int, input().split()))
m = int(input())
find_num = list(map(int, input().split()))

cards_num.sort()
result = []


def lower_bound(arr, target):
    cur_min = 0
    cur_max = len(arr)

    while cur_min < cur_max:
        mid = (cur_min + cur_max) // 2
        if target <= arr[mid]:
            cur_max = mid
        else:
            cur_min = mid + 1

    return cur_min


def upper_bound(arr, target):
    cur_min = 0
    cur_max = len(arr)

    while cur_min < cur_max:
        mid = (cur_min + cur_max) // 2
        if target < arr[mid]:
            cur_max = mid
        else:
            cur_min = mid + 1

    return cur_min


for i in range(m):
    result.append(upper_bound(cards_num, find_num[i]) - lower_bound(cards_num, find_num[i]))

print(*result)

2. bisect를 사용한 풀이

from bisect import bisect_left,bisect_right

n = int(input())
cards_num = list(map(int, input().split()))
m = int(input())
find_num = list(map(int, input().split()))
cards_num.sort()
result = []

for i in range(m):
    result.append(bisect_right(cards_num, find_num[i]) - bisect_left(cards_num, find_num[i]))

print(*result)

3. dictionary를 사용한 풀이

n = int(input())
cards_num = list(map(int, input().split()))
m = int(input())
find_num = list(map(int, input().split()))

dicts = {}

for num in cards_num:
    if num in dicts:
        dicts[num] += 1
    else:
        dicts[num] = 1

for num in find_num:
    if num in dicts:
        print(dicts[num], end=' ')
    else:
        print(0, end=' ')

4. Counter를 사용한 풀이

from collections import Counter

n = int(input())
cards_num = list(map(int, input().split()))
m = int(input())
find_num = list(map(int, input().split()))

cnt = Counter(cards_num)

for num in find_num:
    if num in cnt:
        print(cnt[num], end=' ')
    else:
        print(0, end=' ')