출처 : https://www.acmicpc.net/problem/10816
문제부터 분석해볼까요?
우선 N, M의 조건과 시간 제한 조건을 먼저 분석해보겠습니다.
N, M의 경우 각각 500000까지 제한이 되어있고, 시간 제한 조건의 경우 1초로 제한이 되어있기 때문에 1억회의 연산 내로 알고리즘을 구성해야합니다.
그러나, N, M의 조건이 500000까지 허용이 되어있는 상황이기 때문에, O(NlogN)으로 구현하는 것이 아닌 이상에는 힘들어보이는 상황입니다. 그러나, O(NlogN)의 알고리즘의 대표는 이진탐색 인데, 이진탐색으로는 이 문제 해결에는 한계가 분명히 존재합니다. 이유는, 위 문제는 탐색을 하는 것도 중요하지만, 탐색을 하여서 그 값이 실제로 몇 개가 있는지까지 구해줘야하기 때문입니다
위 문제의 경우에는 저는 두 가지 해결법을 생각해보았는데요, 해결법은 다음과 같습니다.
- 투포인터로 알고리즘을 구성한다. 일단 두 리스트를 먼저 정렬을 해 준 다음에, 두 리스트에 대해서 투포인터 기법으로 탐색을 해가면서, 빠르게 탐색을 끝내버린다.
- dictionary 자료형을 이용해서 알고리즘을 구성한다.
위의 두 해결 전략 중에, 투포인터의 경우에는 구현의 복잡도가 상당히 큰 것을 알수있으며, 두번째 방법이 훨씬 편하고 복잡도를 낮게 가져갈 수 있기 때문에, 저는 이 문제 해결 전략으로 두 번째인 딕셔너리를 이용한 문제 해결 전략을 채택하였습니다.
그러면, 코드를 확인해보겠습니다!
코드를 확인해보겠습니다
import sys
input = sys.stdin.readline
N = int(input())
having_list = list(map(int, input().split()))
having_dict = {}
M = int(input())
search_list = list(map(int, input().split()))
# having_dict에 정보 넣기
for number in having_list:
if number not in having_dict.keys():
having_dict[number] = 1
else:
having_dict[number] += 1
for search_number in search_list:
if search_number in having_dict.keys():
print(having_dict[search_number], end=' ')
else:
print(0, end=' ')우선, 가지고 있는 숫자 카드 리스트를 딕셔너리로 변환을 시킵니다. 그리고 딕셔너리에는 key 값으로 숫자 카드의 값을, value 값으로는 숫자 카드의 개수를 저장합니다.
그 후에, 두 번째로 입력받은 리스트에서 숫자를 하나씩 순회하면서, dict에서 key로 현재 순회중인 값이 존재하는 경우에는 값을 그대로 출력을 해주고, 없는 경우에는 0을 출력해주게 되면, 문제는 모두 해결이 됩니다.
간단하죠?
