17. Python(숫자2)

[toc]

숫자2

문제

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

---

제출

코드1

import sys

input = sys.stdin.readline

n = int(input())
n_lst = list(map(str, input().split()))
# print(n_lst)

m = int(input())
m_lst = list(map(str, input().split()))
# print(m_lst)

rst = []
for integer_m in m_lst:
    cnt = 0
    for i in range(len(n_lst)):
        if integer_m == n_lst[i]:
            cnt += 1
        else:
            pass
    rst.append(cnt)

print(*rst)

# 입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

# 출력
3 0 0 1 2 0 0 2

---

인사이트

1. n개의 수와 m개의 수를 받은 후 각각 n_lst와 m_lst에 입력함

2. m_lst에 있는 수가 n_lst에 반복되는 횟수를 rst리스트에 저장 후 공백을 기준으로 한 줄에 출력함

3. 그러나 출력시 시간 초과가 발생하는 것을 알았음

   • 중첩된 반복문이 시간 복잡도가 O(N x M)을 가지는 것을 확인함
   • 불필요한 연산을 줄이기 위해 for 반복문 말고 다른 방법을 생각했음

풀이

딕셔너리를 활용하여 요소의 빈도 확인

• collections.Counter나 딕셔너리를 사용하여 리스트 n_lst의 각 요소의 빈도를 미리 계산해 두고, m_lst를 순회할 때 바로 조회하는 것이 효율적임

코드2

import sys
from collections import Counter

input = sys.stdin.readline

n = int(input())
n_lst = list(map(str, input().split()))

m = int(input())
m_lst = list(map(str, input().split()))

count_dict = Counter(n_lst)

rst = [count_dict[integer_m] for integer_m in m_lst]

print(*rst)

# 입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

# 출력
3 0 0 1 2 0 0 2

collections.Counter 사용

• Counter를 사용하여 n_lst의 각 요소의 빈도를 계산합니다. Counter는 딕셔너리 형태로, 각 요소를 키로, 그 빈도를 값으로 저장
• Counter(n_lst)의 시간 복잡도는 O(N)

m_lst 조회

• m_lst를 순회하면서 count_dict[integer_m]로 해당 요소의 빈도를 바로 조회
• 딕셔너리의 조회 시간 복잡도는 O(1)
• 따라서 전체 시간 복잡도는 O(N + M)

---