[➕ 오답노트] 백준 11478번

👇🏻 문제

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

11478번: 서로 다른 부분 문자열의 개수

---

간단하지만, 시간초과와 싸워야 하는 문제이다.

나는 당연히 2중 포문을 사용해서 코드를 작성했지만, 항상 공개되어 있는 정답코드와 비교해보곤 한다.

 

# Nesty Code : 508ms
import sys

str = sys.stdin.readline().strip()
combi = {}

for i in range(1,len(str)+1):
    for j in range(len(str)-i+1):
        combi[str[j:j+i]]=0

print(len(combi))

 

#Clean Code : 260ms
import sys

str = sys.stdin.readline().strip()
print(sum(len({str[i:i+gap] for i in range(len(str)+1-gap)}) for gap in range(1, len(str)+1)))

 

그 중 이 정답코드가 눈에 띄었다.

이 코드의 sum(len( ... )) 중 ... 부분에 있는 코드는 내 코드와 유사하지만 set을 이용해서 중복을 제거해주었다.

 

{str[i:i+gap] for i in range(len(str)+1-gap)} for gap in range(1, len(str)+1))

# {'b', 'a', 'c'}, {'bc', 'ab', 'ba'}, {'abc', 'aba', 'bab'}, {'abab', 'babc'}, {'ababc'}

 

각각의 len의 합 3 + 3 + 3 + 2 + 1 이 정답이 된다.

천잰가?