본문 바로가기

환영합니다. 이 블로그 번째 방문자입니다.
Python/문제풀이

[➕ 오답노트] 백준 11478번

👇🏻 문제

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

 

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

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

www.acmicpc.net


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

나는 당연히 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 이 정답이 된다.

천잰가?