백준 1251 단어 나누기 Python

🐸 문제 정보

1251번: 단어 나누기

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

31.25m

 

📝 풀이

그리디처럼 풀면서 최적의 방법을 찾다가... 계속 틀리길래 '이게 맞나'란 생각이 들었다.

알고보니 그냥 생구현으로 풀 수 있는 아주 쉬운 문제였다ㅠㅠ

처음에는, 단어를 정렬해서 사전 순 앞에 나오는 문자의 인덱스를 뒤에서 부터 찾아내고 잘라서 넣는.. 과정을 거쳤다.

 

틀린 풀이

import sys
input = sys.stdin.readline

word = input().rstrip()
sw = sorted(word)
i = 0
idx = 0
cnt = 0
res = ''

while cnt < 2:
    if (cnt == 0) and (sw[i] in word[idx:-2]):
        temp = word[idx:-2].rindex(sw[i])
        res += word[idx:temp + 1][::-1]
        idx += temp + 1
        cnt += 1
    elif (cnt == 1) and (sw[i] in word[idx:-1]):
        temp = word[idx:-1].rindex(sw[i])
        res += word[idx:idx + temp + 1][::-1]
        idx += temp + 1
        cnt += 1
    i += 1

res += word[idx:][::-1]
print(res)

해답은 그냥 간단하게 자르는 구간 총 2개를 반복문 돌려서 찾아보고, 직접 정렬해서 실제로 사전순 앞에 있는 문자열을 고르면 되는 아주... 간단한 문제였다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

word = list(input().rstrip())
lw = len(word)
res = []

for i in range(1, lw - 1):
    for j in range(i + 1, lw):
       res.append(''.join(word[:i][::-1] + word[i:j][::-1] + word[j:][::-1]))

print(sorted(res)[0])