10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
지난번에 풀었던 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=' ')HongEunho - Overview
📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.
github.com
전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
'Algorithm > Binary Search' 카테고리의 다른 글
| [백준] 12015번 가장 긴 증가하는 부분 수열 2 (Python 파이썬) (0) | 2021.04.04 |
|---|---|
| [백준] 1300번 K번째 수 (Python 파이썬) (0) | 2021.04.04 |
| [백준] 1654번 랜선 자르기 (Python 파이썬) (0) | 2021.01.27 |
| [백준] 3020번 개똥벌레 (Python 파이썬) (0) | 2021.01.25 |
| [백준] 10815번 숫자 카드 (Python 파이썬) (0) | 2021.01.24 |
