[백준] 10816번 숫자 카드 2 (Python 파이썬)

 

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

지난번에 풀었던 10815번 숫자카드 1 문제의 상위 호환 문제이다.

숫자카드1 문제의 경우 이진탐색을 하여 찾고자 하는 숫자가 있으면 단순히 1을 출력하는 문제였다면,

이 문제는 찾고자 하는 숫자의 개수까지 구해야 한다.

 

<방법1>

처음에는 숫자카드 1처럼 이진탐색을 한 후에 찾은 숫자는 리스트에서 제외를 해주고 다시 이진탐색을 추가하는 식으로 해서 개수를 구했는데, 이진탐색임에도 불구하고 시간초과 오류가 났다.

 

<방법2>

그래서 다음으로 찾은 방법은

이진 탐색을 진행하여 찾고자하는 숫자를 찾게되면 그 숫자만 count함수를 이용해서 개수를 구한 방법이다.

코드는 첨부하지만, 이 방법도 40%쯤 지나갔을 때 시간초과 오류가 발생했다.

from sys import stdin
n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

card.sort()

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

for i in range(len(test)):
    a = binary_search(card, test[i], 0, len(card)-1)
    if a is not None:
        print(a, end=' ')
    else:
        print(0, end=' ')

 

<방법3>

그래서 다음으로 찾은 방법은,

파이썬 내장 모듈인 bisect를 이용해서 풀었고, 시간초과 오류 없이 통과하였다.

bisect는 파이썬에 내장되어있는 이진탐색 모듈인데

bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스,

bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 알려준다.

 

이를 이용하여 count_by_range라는 함수를 만들어 주었는데

이 함수의 인자인 left_value와 right_value 사이에 존재하는 숫자들의 갯수를 반환하는 함수이다.

따라서 left_value와 right_value에 같은 값을 주게 되면 그 숫자의 갯수를 세게 되는 것이다.

from bisect import bisect_left, bisect_right
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))
card.sort()

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


for i in range(len(test)):
    print(count_by_range(card, test[i], test[i]), end=' ')

 

<방법4>

파이썬 내장 모듈인 Counter 이용

Counter는 리스트를 값으로 주게 되면 해당 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환한다.

from collections import Counter
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

count = Counter(card)

for i in range(len(test)):
    if test[i] in count:
        print(count[test[i]], end=' ')
    else:
        print(0, end=' ')

 

<방법5>

해쉬맵 이용 ( 파이썬에서는 딕셔너리 )

방법4의 Counter와 비슷하지만 직접 해쉬맵을 만들어 구현하였다.

from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

hash = {}

for i in card:
    if i in hash:
        hash[i] += 1
    else:
        hash[i] = 1

for i in test:
    if i in hash:
        print(hash[i], end=' ')
    else:
        print(0, end=' ')

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !