[백준] 32953번 - 회상, python

문제

백준 32953번 '회상' 문제는 각 사람의 기억 속에 있는 숫자들을 종합해,

m명 이상이 기억하고 있는 숫자의 개수를 세는 문제다.

 

처음에는 딕셔너리를 이용해 풀었으나 시간 초과가 발생했고, 이후 list와 set 조합으로 해결했다.

---

오답코드

n,m = map(int, input().split(' '))
dic = {}
result = 0

for i in range(n) :
    num = int(input())
    li = input().split(' ')
    for j in range(num) :
        if li[j] in dic :
            dic[li[j]] += 1
        else :
            dic[li[j]] = 1
    

for key, value in dic.items() :
    if value >= m :
        result +=1

print(result)

문제점

• li[j] in dic 탐색에서 시간복잡도 증가
• 반복적으로 탐색 & 갱신하면서 누적 시간 증가
• 결국 시간초과 발생

---

정코드

n,m = map(int, input().split(' '))
array = []
set = set()
sum = 0

for i in range(n) :
    num = int(input())
    array1 = list(map(int,input().split(' ')))
    array += array1
    set.update(array1)

for i in set :
    if array.count(i) >= m :
        sum += 1

print(sum)

설명

리스트와 집합(set)을 함께 활용하여 불필요한 중복 탐색을 줄이고,

시간복잡도를 효율적으로 관리함으로써 통과할 수 있었다.

=> 여기서 딕셔너리 사용시 시간복잡도 O(1)인데, 딕셔너리 사용하면 O(N)으로 다름