백준 25192 인사성 밝은 곰곰이(Defaultdict와 list차이)

백준 25192

문제 내용은 생략하겠습니다.

 import sys
 input = sys.stdin.readline
 n = int(input())
 chat_dialogue = []

 for _ in range(n):
     chat = input()
     chat_dialogue.append(chat)
  print(chat_dialogue)
 ref_list = ["ENTER"]
 count = 0
 for i in range(1,n):
     if "ENTER" in ref_list and chat_dialogue[i] not in ref_list:
         count += 1
         ref_list.append(chat_dialogue[i])
     elif chat_dialogue[i] == "ENTER" and "ENTER" in ref_list:
         ref_list.clear()
         ref_list.append("ENTER")
print(count)

리스트로 쉽게쉽게 풀었더니 시간초과가 발생했다!

그래서 힌트를 얻으려고 이리저리 뛰어다녔더니,, 리스트로 푸셨나요? 라는 힌트를 얻을 수 있었고, dictionary형식으로 풀어보려고 했다.

from collections import defaultdict

n = int(input())
chat_dialogue = []

for _ in range(n):
    chat = input().rstrip()  
    chat_dialogue.append(chat)

ref_list = ["ENTER"]
count = 0
seen = defaultdict(int)

for chat in chat_dialogue[1:]:
    if chat == "ENTER":
        ref_list = ["ENTER"] 
        seen.clear()
    elif chat not in seen and "ENTER" in ref_list:
        count += 1
        seen[chat] = 1
        ref_list.append(chat)

print(count)

이러니까 통과가 되었고, list와 dictionary의 차이를 알아보려고 했다.

List와 Dictionary의 차이

리스트:
삽입 (append): O(1)
조회 (indexing): O(1)
삭제 (remove): O(n)
탐색 (in 연산): O(n)

defaultdict:
삽입 (key-value pair 추가): O(1)
조회 (key-value pair 검색): O(1)
삭제 (key-value pair 삭제): O(1)
탐색 (in 연산): O(1)

1. 시간복잡도

• 리스트와 defaultdict 모두 삽입, 조회, 삭제의 경우에 O(1)의 시간 복잡도를 갖습니다.
• 하지만 리스트에서 삭제 연산은 해당 요소를 찾기 위해 순차적으로 탐색해야 하므로 O(n)의 시간이 소요됩니다.
• 따라서 많은 요소를 삭제해야 하는 경우에는 리스트보다 defaultdict가 효율적입니다.

2. 그래서 결론은?

• 탐색(검색) 연산에서도 defaultdict가 리스트보다 효율적입니다.
• 리스트의 경우 요소를 하나씩 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도가 필요하지만, defaultdict에서는 키를 사용하여 직접 검색하므로 O(1)의 시간이 소요됩니다.

3. 하지만...

• 따라서 일반적으로 많은 요소를 추가하고 삭제하는 작업이 필요하거나 탐색 속도가 중요한 경우, defaultdict를 사용하는 것이 더 효율적입니다.
• 하지만 순차적인 데이터 저장 및 접근이 필요한 경우에는 리스트가 더 적합할 수 있습니다.
• 즉, 사용 목적에 따라 적절하게 선택하여 사용하는 것이 중요합니다.