[백준] 1764번 듣보잡 / set() 집합의 시간복잡도

 

 

가끔 알고리즘 문제를 풀었지만 오랜만에 포스팅 합니다. 

 

이번 문제에서 놓치고 있던 지식을 상기시켰습니다. 바로 자료형의 시간 복잡도 입니다. 

기존에 시간초과가 발생했을 때 주로 입력부분과 불필요한 반복문에서 시간초과가 많이 발생하여 자료형에 따른 시간 복잡도를 놓쳤습니다. 이번 문제로 한번 더 상기시킬 수 있는 기회였습니다.

 

시도 1.  input(), list() 활용 - 시간초과로 실패

n,m = map(int, input().split())
n_lst = [ input() for _ in range(n)]
m_lst = [ input() for _ in range(m)]

lst = n_lst + m_lst
lst.sort()
total_lst = []
for i in lst :
    if lst.count(i) == 1 :
        total_lst.append(i)

print(len(total_lst))
for w in total_lst:
    print(w)

 

 

시도 2. sys.stdin.readline(), list() 활용 - 시간초과로 실패

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
lst = []
for _ in range(n+m):
    lst.append(input().strip())

total_lst = []

for i in lst :
    if lst.count(i) > 1 :
        lst.remove(i)
        total_lst.append(i)

total_lst.sort()
print(len(total_lst))
for w in total_lst:
    print(w)

 

 

시도 3. sys.stdin.readline(), set() 활용 - 성공!

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
n_set = set()
m_set = set()

for _ in range(n):
    name = input().strip()
    n_set.add(name)
for _ in range(m):
    name = input().strip()
    m_set.add(name)
    
ans = list(n_set & m_set)
ans.sort()

print(len(ans))
print(*ans, sep="\n")

 

 

자료형의 시간 복잡도

리스트와 집합의 메서드별 시간복잡도

 

자료형별 차이가 있는 메서드 : 삽입, 제거, 탐색, 포함 여부 확인

• list, tuple : O(n)
• set, dict : O(1)

 

Tip !

탐색과 포함여부 확인을 위한 연산이면  set이나 dictionary 사용

삽입과 제거처럼 순서가 필요하다면 list 사용

 

 

 

- 참고링크 : https://chancoding.tistory.com/43