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

 

1. 첫 번째 시도

S = input()
lst = []
temp = 1
for i in range(len(S)):
    start, end = 0, temp
    while(end <= len(S)):
        lst.append(S[start : end])
        start += 1
        end += 1
    temp += 1
    lst = list(set(lst)) # 중복 제거

print(len(lst))

 

입력받은 문자열을 S 라 하고, for문에서 슬라이싱 하는 모든 원소들을 저장할 리스트를 lst라고 하였다.

아래 예시와 같이 len(S) 번 만큼 반복하며 슬라이싱 한 문자열을 리스트에 넣는 작업을 하기 위해, start와 end를 동적으로 이용하였음

 

a[0:1], b[1:2], a, b, c, 
ab[0:2], ba[1:3], ab, bc, 
aba[0:3], bab[1:4], abc[2:5], 
abab, babc, 

ababc

 

그리고 채워진 lst에 중복된 원소가 없어야 하므로 list(set(lst))로 중복을 for 루프에서 매번 처리했다.

 

위 코드에서 시간 초과 오류가 발생한 이유는 코드에서 중복 제거를 위해 매번 list(set(lst))를 사용했기 때문이었다고 판단하여 없애버렸고, 이중 루프에서 매번 슬라이싱을 하는 작업 또한 비효율적이라고 판단되었다.

따라서 위 아이디어를 기반으로 수정해서 다음과 같은 최종 코드를 작성하였음

 

 

2. 최종 정답 코드

S = input()
string = set() # 문자열들을 저장할 집합
for i in range(len(S)):
    for j in range(i+1, len(S) + 1):
        string.add(S[i:j])

print(len(string))

 

• 중복 제거를 첫 번째 코드처럼 리스트로 변환한 후에 하는 대신에, 애초에 처음부터 집합 set을 사용하여 중복을 방지
• 슬라이싱과 중복 제거를 효율적으로 처리하기 위해 문자열들을 저장하는 string 이라는 집합 생성
• 이중 루프에서 S[i : j]로 부분 문자열을 추출하여 집합에 바로 추가하도록 함
  • 이렇게 하면 집합은 중복된 요소를 자동으로 처리하기 때문에 추가적인 중복 제거 작업이 필요하지 않음!