[Python] [백준] 10816번 - 숫자 카드 2 (여러가지 사용)

숫자 카드 2

하위호환 문제: 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

---

1. 틀린 코드의 역사 - 시간초과

1. 직관적인 생각대로 가장 간단하게 구현하고자 함

속도를 높이기 위해 입력은 sys로 받고...

list보다 tuple이 더 빠르다는 말을 들은 적이 있어서 tuple을 이용했다.

그러나 tuple은 변경이 불가하다.

그래서 출력을 위한 cnt_N을 새로 만들어 주었다.

 

핵심원리: arr_M에 있는 각각의 원소가 arr_N에 몇 개 있는지 세는 문제이므로

arr_N에 있는 수들을 세어주기 위해 arr_N.count(arr_M[i]) 를 사용하고,

여기서 반환된 값을 새로운 list인 cnt_N에 넣어준다.

그리고 *을 이용하여 원소만 띄어쓰기하여 출력함

 

-> 시간초과....

아마 count를 할 때 arr_N의 원소개수만큼 탐색 시간이 걸려서 그런듯 하다

시간복잡도는 O(MxN)?

 

import sys

N = int(sys.stdin.readline().strip())
arr_N = tuple(map(int, sys.stdin.readline().strip().split()))
M = int(sys.stdin.readline().strip())
arr_M = tuple(map(int, sys.stdin.readline().strip().split()))
cnt_N = []

for i in range(M):
    cnt_N.append(arr_N.count(arr_M[i]))

print(*cnt_N)

 

2. 이진탐색을 사용함

이진탐색을 사용하기 위해 입력받자마자 sorted를 하였다.

target을 찾으면, 개수를 세야 하는 원소들이 들어있는 arr_N (함수 안에서는 arr)을

슬라이싱을 통해 start부터 end까지 count를 하여 개수를 센다.

 

근데... 이렇게 하면, target이 10이고

[..., 10, 10, 10, ...] 이렇게 원소가 들어있을 때

이진탐색을 하다가 첫번째 10을 지나치고, 두번째 10부터

start를 매겨서 제대로 count를 못할 수도 있지 않을까..? 라는 생각이 들었다.

 

아니다. mid index는 이전의 10을 지나칠 수 있지만

이미 이전 횟수의 이진탐색에서 10이 없었기에 다음 이진탐색을 한 것이고,

10을 찾았을 때의 start, end 범위 전체에서 탐색하여 개수를 세므로 문제없다.

 

하지만... 이진탐색을 해도 시간초과가 나온다.

이진탐색의 시간복잡도는 O(logN)이지만, count하는 과정에서 또

시간이 오래 걸린 것 같다.

import sys

N = int(sys.stdin.readline().strip())
arr_N = sorted(map(int, sys.stdin.readline().strip().split()))
M = int(sys.stdin.readline().strip())
arr_M = tuple(map(int, sys.stdin.readline().strip().split()))
cnt_N = [0 for _ in range(M)]

def binary_countNum(arr, target, start, end):
    if start > end:
        return 0
    mid = (start+end)//2
    if target == arr[mid]:
        return arr[start:end+1].count(target)
    elif target < arr[mid]:
        return binary_countNum(arr, target, start, mid-1)
    elif target > arr[mid]:
        return binary_countNum(arr, target, mid+1, end)


for i in range(M):
    if arr_M[i] not in arr_N:
        continue
    cnt = binary_countNum(arr_N, arr_M[i], 0, N-1)
    cnt_N[i] += cnt

print(*cnt_N)

 

3. 똑같은 코드지만 속도를 높이기 위해...

deque를 사용해보았다.

그러나 count 방식은 같기에 시간초과 나옴.

from collections import deque
import sys

N = int(sys.stdin.readline().strip())
arr_N = sorted(map(int, sys.stdin.readline().strip().split()))
M = int(sys.stdin.readline().strip())
arr_M = deque(map(int, sys.stdin.readline().strip().split()))
cnt_N = [0 for _ in range(M)]

def binary_countNum(arr, target, start, end):
    if start > end:
        return 0
    mid = (start+end)//2
    if target == arr[mid]:
        return arr[start:end+1].count(target)
    elif target < arr[mid]:
        return binary_countNum(arr, target, start, mid-1)
    elif target > arr[mid]:
        return binary_countNum(arr, target, mid+1, end)


for i in range(M):
    if arr_M[i] in arr_N:
        cnt_N[i] += binary_countNum(arr_N, arr_M[i], 0, N-1)

print(*cnt_N)

---

2. 맞은 코드의 역사

1. bisect를 사용함

bisect의 시간복잡도는 O(logN) 이다.

from bisect import bisect_left, bisect_right
from sys import stdin

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

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

# card 리스트에서 bisect를 이용해 test에서 뽑아낸 값(i)의
# 좌우 index를 알아내어 index의 차이만큼 반환하면
# 그 차이가 곧 개수다.
for i in test:
    print(count_by_range(card, i, i), end=' ')

 

2. Counter를 사용함

이전의 count()는 시간복잡도가 O(N)이라서

이 count()를 여러번 반복한다면 반복할 때마다

list 전체를 탐색하므로 O(N²)이다.

 

하지만 Count 컬렉션은 딕셔너리로 애초에 한 번 정리할 때 O(N)이지만

정리된 것을 조회할 때는 O(1)이라서 총 O(N)의 시간복잡도를 가진다.

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()))

# Counter는 리스트를 값으로 주게 되면
# 해당 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환한다.
# {원소:개수, ...} 형태다. 개수의 내림차순으로 정렬된다.
count = Counter(card)
# Counter({10: 3, 3: 2, -10: 2, 6: 1, 2: 1, 7: 1})

# test에서 하나씩 뽑아낸 값(i)이
# card의 각 원소 개수를 세어 저장한 count에
# 있는지 확인하여 있다면 그 개수를, 없다면 0을 출력한다
# 딕셔너리로 저장된 원소(수)를 입력하면 그에 해당하는 값(개수)이 출력된다.
for i in test:
    if i in count:
        print(count[i], end=' ')
    else:
        print(0, end=' ')

 

3.  hash (딕셔너리) 를 사용함

hash map을 이용했지만, 이 역시 딕셔너리에 저장해놓고 사용하는 방식이라

O(N)의 시간복잡도를 가진다.

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

# print(hash)
# {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}
# 딕셔너리 자체를 사용하면 입력받은 순서대로 정렬된다.
# 6 3 2 10 -10 7 

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