[백준/Python] 11478번 서로 다른 부분 문자열의 개수 문제

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

 

출처: 백준 11478번 서로 다른 부분 문자열의 개수

 

 

■ 코드 풀이 #1 (2346ms)

 

중첩 for문을 활용하면 문제를 풀 수 있습니다. 중복을 허용하지 않으므로 우선 set을 하나 선언하고요. 1부터 문자열의 길이까지 하나씩 증가하면서 문자열을 slicing 하여 결괏값을 set에 넣어주면 됩니다.

저 같은 경우에는 반복문의 횟수를 줄이기 위해 2부터 시작했습니다. 문자의 개수가 1개일 때는 단순하게 set(문자열)을 하면 되고, 문자열의 개수가 문자열의 길이와 동일한 경우는 그냥 1개니까요. 최종 출력에서 더해줬습니다.

그런데 풀이 시간이 2346ms나 걸렸네요. 왜 이렇게 오래 걸렸는지 생각해 보니 join 때문이었습니다. 생각해 보면 굳이 join을 할 필요가 없는데 왜 썼을까요.. 'ab'나 ['a', 'b']나 set 입장에서는 같은 한 개의 원소인데. 

S = input()
num_sets = set()

for i in range(2,len(S)):
    for j in range(len(S)-i+1):
        num_sets.add(''.join(S[j:j+i]))
    
print(len(num_sets) + len(set(S)) + 1)

 

■ 코드 풀이 #2 (512ms)

 

그래서 위의 코드에서 join만 제거했습니다. 그랬더니 알고리즘 속도가 눈에 띄게 개선되었습니다. 역시 알고리즘 문제는 항상 문제를 쫓아가면 안 되고 스마트하게 풀어야 하나 봅니다.  

S = input()
num_sets = set()

for i in range(2,len(S)):
    for j in range(len(S)-i+1):
        num_sets.add(S[j:j+i])
    
print(len(num_sets) + len(set(S)) + 1)