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

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

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

 

• 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하기
• 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 함
• 예를 들어, ababc의 부분 문자열은
  • a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고
  • 서로 다른것의 개수는 12개

• 입력
  • 첫째 줄에 문자열 S가 주어짐
  • S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하
• 출력
  • 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력
• 시간 제한: 1초
• 메모리 제한: 512 MB

 

"""
입출력 예시)

ababc -> 12
"""

 

 

## 의사코드 ##

# 서로 달라야 함
# set()

# 부분 문자열
# for i in range(len(string)):
#     for j in range(i, len(string)):
          #i번째 문자부터 부분문자열 구하기
#         li.add(string[i:j+1])

 

 

 

통과한 코드

 

string = input()
li = set()

for i in range(len(string)):
    for j in range(i, len(string)):
        #i번째 문자부터 부분문자열 구하기
        li.add(string[i:j+1])

print(len(li))

 

 

• 과정 확인

"""
a 

{'a'} 

--------------------------------------------------
ab 

{'a', 'ab'} 

--------------------------------------------------
aba 

{'a', 'aba', 'ab'} 

--------------------------------------------------
abab 

{'a', 'aba', 'ab', 'abab'} 

--------------------------------------------------
ababc 

{'aba', 'ab', 'ababc', 'abab', 'a'} 

--------------------------------------------------
b 

{'aba', 'ab', 'ababc', 'abab', 'b', 'a'} 

--------------------------------------------------
ba 

{'aba', 'ba', 'ab', 'ababc', 'abab', 'b', 'a'} 

--------------------------------------------------
bab 

{'aba', 'ba', 'ab', 'ababc', 'abab', 'bab', 'b', 'a'} 

--------------------------------------------------
babc 

{'babc', 'aba', 'ba', 'ab', 'ababc', 'abab', 'bab', 'b', 'a'} 

--------------------------------------------------
a 

{'babc', 'aba', 'ba', 'ab', 'ababc', 'abab', 'bab', 'b', 'a'} 

--------------------------------------------------
ab 

{'babc', 'aba', 'ba', 'ab', 'ababc', 'abab', 'bab', 'b', 'a'} 

--------------------------------------------------
abc 

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

--------------------------------------------------
b 

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

--------------------------------------------------
bc 

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

--------------------------------------------------
c 

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

--------------------------------------------------
"""

 

 

 

 

 

참고)

 

https://velog.io/@yj_lee/%EB%B0%B1%EC%A4%80-11478%EB%B2%88-%EC%84%9C%EB%A1%9C-%EB%8B%A4%EB%A5%B8-%EB%B6%80%EB%B6%84-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%98-%EA%B0%9C%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 11478번 : 서로 다른 부분 문자열의 개수 (파이썬)