[Daily 코테] 백준 1251번: 단어 나누기

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

1251번: 단어 나누기

First Try

word = input() #변수 word에 단어를 입력받는다.
std1 = word.index(sorted(word)[0]) #알파벳순으로 word를 sort하여 가장 앞쪽 문자를 std1에 저장한다.
std2 = word.index(sorted(word)[1]) #그 다음에 있는 문자를 저장한다.
#문제의 조건 중 "이렇게 만들어진 단어들 중, 가장 앞서는 단어를 출력"이 있다.
#해당 조건을 충족시키기 위해서는 앞쪽 순서에 있는 알파벳(abc...)이 나올 때마다 단어를 끊어줘야한다.
#그래야 나눈 단어들의 앞뒤를 뒤집을 때마다 앞쪽 순서 알파벳이 앞으로 이동하기 때문이다.

front = min(std1,std2) #std1와 std2 중 word에서 더 앞쪽에 있는 문자를 저장한다.
back = max(std1,std2) 
#만약 이 과정없이 std1,std2로 슬라이싱을 한다면, 나눠진 단어들 중 겹치는 부분이 생길 것이다.

one = (word[0:front+1])[::-1]
two = (word[front+1:back+1])[::-1]
three = (word[back+1:])[::-1]
#나눈 세 단어들의 앞뒤를 뒤집는다.

print(one+two+three)

Test case

cba

=> 단어를 세개로 나누지 않기 때문에 틀렸다.

Second Try

word = input()
n = 0
while (True):
    std1 = word.index(sorted(word)[n])
    one = word[:std1+1]
    if len(one)==0 or len(one)==len(word):
        n += 1
        continue
    else:
        std2 = word.index(sorted(word)[n+1])
        if sorted(word)[n+1] in one:
            one = word[:std2+1]
            two = word[std2+1:std1+1]
            three = word[std1+1:]
        else:
            two = word[std1+1:std2+1]
            three = word[std2+1:]
        break

one = one[::-1]
two = two[::-1]
three = three[::-1]

print(one+two+three)

Test Case 1

dcaaaba

=> 작은 알파벳이 연속으로 나오는 경우

Test Case 2

cadacaca

=> 작은 알파벳이 3번 이상 나오는 경우

두 케이스 모두 index 함수가 더 앞쪽에 있는 인덱스를 추출하기 때문에 에러가 발생한다.

 

Third Try🎉

word = input()
result = 'z' * len(word)
for i in range(len(word)):
    one = word[:i+1][::-1]
    for j in range(i+1,len(word)-1):
        two = word[i+1:j+1][::-1]
        three = word[j+1:][::-1]
        result = min(result, (one+two+three))
print(result)

아예 갈아엎었다. 두번째 시도에서 발견한 test case를 통해 생각해야하는 조건이 너무 많다는 것을 깨달았다. 그래서 아예 하나씩 비교하는 방법을 선택했다.

---

설마 이렇게까지 비효율적으로? 라는 것들이 정답일 때도 있다. 특히 최근에 푼 문제들을 끝까지 혼자 힘으로 해내지 못한게 이를 간과했기 때문인 것 같다.