[Python] 백준 11656번_접미사 배열

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

11656번: 접미사 배열

 

• 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열
• baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고
  • 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon
• 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력

• 입력
  • 첫째 줄에 문자열 S가 주어짐
  • S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같음
• 출력
  • 첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력
• 시간 제한: 1초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

baekjoon
        -> aekjoon
           baekjoon
           ekjoon
           joon
           kjoon
           n
           on
           oon
"""

 

 

## 의사코드 ##

# 접미사 생성 -> 인덱스로 슬라이싱 

# suffixs = [] # 접미사를 담을 리스트
# for i in range(1, len(s)):
#     suffixs.append(s[i:])

# 접미사 리스트 사전순으로 정렬
# suffixs.sort() 

# for suffix in suffixs:
#     print(suffix )

 

 

 

첫 번째 시도

 

s = input()

suffixs = [] # 접미사를 담을 리스트
# 접미사 생성
for i in range(1, len(s)):
    suffixs.append(s[i:])

# 접미사 리스트 사전순으로 정렬
suffixs.sort() 
# 접미사 순서대로 출력
for suffix in suffixs:
    print(suffix)

 

-> 틀림

 

baekjoon의 접미사는 baekjoon도 포함되어야 하는데 맨 첫 번째 글자를 제외한 것을 접미사로 생성해서 틀림 (문제를 잘못 읽음)

 

 

 

통과한 코드

 

s = input()

suffixs = [] # 접미사를 담을 리스트
# 접미사 생성 (자기 자신도 접미사에 포함)
for i in range(len(s)):
    suffixs.append(s[i:])

# 접미사 리스트 사전순으로 정렬
suffixs.sort() 
# 접미사 순서대로 출력
for suffix in suffixs:
    print(suffix)

 

-> 접미사를 생성할 때, 자기 자신도 포함하기 위해 for i in range(len(s)) 로 수정