[Python][백준/BOJ] 22233번 : 가희와 키워드

https://www.acmicpc.net/problem/22233

22233번: 가희와 키워드

 

내 코드

시간 초과된 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
a=set(input().strip('\n') for _ in range(n))
blog = list(input().rstrip('\n').split(',') for _ in range(m))
b=set()
for i in blog:
    for j in i:
        b.add(j)
    print(len(a-b))

 

통과된 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())

memo={}
for i in range(n):
    a= input().strip()
    memo[a] = ""
    
for _ in range(m):
    b = input().strip().split(',')
    for i in range(len(b)):
        if b[i] in memo:
            del memo[b[i]]
    print(len(memo))

 

코드 리뷰

어쩐지 너무 쉽다 했다.

set를 통해 중복을 거르고, 걸러진 두 set를 차집합으로 연산하면 답이 나오기 때문에 그렇게 해결하려고 했다.

그리고 시간초과가 발생했다.

 

set 시간 복잡도

set의 시간복잡도

• 리스트에서의 x in s 연산의 평균 시간 복잡도 : O(n)
• 세트에서의 x in s 연산의 평균 시간 복잡도 : O(1)

나는 for문을 돌렸기 때문에 O(n^2) 가 되었다. 그리고 차집합을 수행했는데, 차집합의 시간복잡도는 O(len(s) + len(t)) 이다. 그래서 시간 초과로 인해 실패했다.

 

dict 시간복잡도

이렇게 시간 초과가 중요하게 여겨지는 문제의 경우에는 dict를 활용해서 푸는 것이 좋다.

dict의 시간복잡도

dict의 시간복잡도를 보면 대부분 O(1)임을 볼 수 있다. 이처럼 확실하게 빠른 탐색이 보장되어 있으니 시간복잡도가 중요하게 여겨지는 문제는 dict를 이용하는 것이 좋다.

 

strip, split

그리고 내가 이 문제를 보면서 strip 과 split 에 대한 이해가 조금 부족했다는 것을 깨달았다.

    b = input().strip().split(',')

이 코드를 보면 변수 b에 list를 씌워주지 않은 채로 바로 strip, split을 사용한다. 나는 이렇게 할 경우 여러 개의 단어를 어떻게 b라는 변수가  저장할 수 있지라는 생각을 했었다.

['map', 'dijkstra']

하지만 막상 결과값을 출력해보니 리스트 안에 자동으로 저장된다. 

strip()

• strip()은 괄호 안에 있는 문자를 기준으로 나눈다.
• trip은 문자열에서만 작동하고 tuple 이나 list에서는 오류가 발생한다.
• 원하는 문자열이나 공백을 제거하기 위해서 사용한다.

 

split()

• split()은 괄호 안에 있는 문자를 기준으로 나누어 list 안에 저장한다.
• 문자열.split(sep=',') 이렇게도 사용할 수 있다.
• 문자를 특정 기준으로 나누어 리스트에 저장하기 위해 사용한다.