10816 숫자 카드 2(Hashmap, Counter)

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

<방법 1 : 단순 리스트 탐색>

#단순 리스트 탐색

n = int(input())
data1 = list(map(int,input().split()))

m = int(input())
data2 = list(map(int,input().split()))

for i in data2:
    temp = data1.count(i)
    print(temp, end=' ')

N과 M이 500,000이기 때문에 단순 리스트 탐색을 이용하면 시간복잡도에서 N^2가 되므로 당연히 시간초과가 난다.

 

 

<방법 2 : 이진 탐색>

#이진 탐색 이용

n = int(input())
data1 = list(map(int,input().split()))

m = int(input())
data2 = list(map(int,input().split()))
data1.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(data2)):
    a = binary_search(data1, data2[i], 0, len(data1)-1)
    if not a == None:
        print(a, end=' ')
    else:
        print(0, end=' ')

이진탐색을 이용해도 시간초과가 나서 내장 모듈을 이용하는 방법을 택하기로 했다.

 

 

<방법 3 : Counter 내장모듈 이용>

#Counter 이용

n = int(input())
data1 = list(map(int,input().split()))

m = int(input())
data2 = list(map(int,input().split()))

from collections import Counter
count = Counter(data1)
print(count)

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

 

Counter 내장모듈의 시간복잡도는 O(N)이기 때문에 시간에 맞춰 탐색이 가능했다.

 

 

<방법 4 : 이진탐색 bisect 내장모듈 이용>

#bisect 내장모듈 이용

import sys
input = sys.stdin.readline

n = int(input())
data1 = list(map(int,input().split()))

m = int(input())
data2 = list(map(int,input().split()))
data1.sort()

from bisect import bisect_left, bisect_right

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(data2)):
    print(count_by_range(data1, data2[i], data2[i]), end=' ')

 

<방법 5 : Hashmap(Dictionary) 이용>

#Hashmap

import sys
input = sys.stdin.readline

n = int(input())
data1 = list(map(int,input().split()))

m = int(input())
data2 = list(map(int,input().split()))

hash = {}

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

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

HashTable(해시 테이블)은 Key 와 Value 의 쌍으로 데이터를 저장하는 자료구조 입니다.
언어에 따라서 HashMap이라고도 불리며, 파이썬의 Dictionary 또한 HashTable로 구현되어 있습니다.

HashTable(HashMap, Dictionary)의 특징은 다음과 같습니다.

• 순차적으로 데이터를 저장하지 않습니다.
• Key를 통해서 Value값을 얻습니다.
• Value값은 중복가능 하지만 Key는 중복될 수 없습니다.
• 수정 가능합니다.(mutable)

파이썬의 List나 자바스크립트의 Array(list)와 달리 저장된 데이터를 순차적으로 찾는게 아니고,
Key값을 통해서 Value값을 찾기 때문에 빠릅니다.