[백준][Python] 1251 단어 나누기

문자열, 브루트포스, 정렬 / 실버 5

🔤

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

1251번: 단어 나누기

 

내 풀이

from itertools import combinations

word = input()
split_length = [x for x in range(len(word)-1)]
split_index = []
split_words = []

for i in combinations(split_length, 2):
    split_index.append(list(i))

for i in range(len(split_index)):
    str1 = word[0:split_index[i][0]+1][::-1]
    str2 = word[split_index[i][0]+1:split_index[i][1]+1][::-1]
    str3 = word[split_index[i][1]+1:][::-1]

    split_words.append(str1+str2+str3)

print(sorted(split_words)[0])

 

 

코드 설명

 

다소 복잡하게 풀었다?

조합(combination)을 사용해서 해결했다.

 

split_length: 0부터 단어의 길이 - 1까지의 정수를 저장하는 리스트. 즉 단어의 인덱스를 의미한다.

split_index: 단어를 쪼갤 두 개의 위치(기준이 되는 인덱스)를 저장하는 이차원 리스트

split_words: 세 개로 쪼개진 단어를 뒤집고 다시 합친 최종 단어를 저장하는 리스트

 

단어의 인덱스들 중 쪼개질 기준이 될 인덱스 2개를 선정한다.

이때 주의해야 할 점은 두 번째 기준 인덱스가 첫 번째 기준 인덱스보다 무조건 커야 한다는 것이다.

예를 들어, (0, 2)는 가능하지만 (2, 0)은 불가능하다.

즉, 순서가 달라도 같은 경우로 간주하는 조합을 사용하는 것이 올바르다.

for i in combinations(split_length, 2):
    split_index.append(list(i))

 

인덱스들의 조합을 기준으로 첫 번째 단어, 두 번째 단어, 세 번째 단어를 구한다.

이때 문자열을 뒤집는 과정을 동시에 진행하였다.

뒤집어진 문자열들을 합쳐서 최종 리스트(split_words)에 저장한다.

for i in range(len(split_index)):
    str1 = word[0:split_index[i][0]+1][::-1]
    str2 = word[split_index[i][0]+1:split_index[i][1]+1][::-1]
    str3 = word[split_index[i][1]+1:][::-1]

    split_words.append(str1+str2+str3)

 

오름차순 정렬 후 맨 앞에 오는 문자열이 사전순으로 가장 앞서는 단어이다.

print(sorted(split_words)[0])

 

 

 

다른 풀이

word = input()
split_words = []

for i in range(1, len(word)-1):
    for j in range(i+1, len(word)):
        str1 = word[:i][::-1]
        str2 = word[i:j][::-1]
        str3 = word[j:][::-1]

        split_words.append(str1+str2+str3)

print(sorted(split_words)[0])

 

이렇게 간단한 방법이 있었다니,,!

굳이 조합을 쓰지 않고도 해결할 수 있었다.

이중 for문에서 바로 쪼개질 기준이 될 인덱스 i, j를 구하여, 세 개의 단어를 구하고, 각각 뒤집고, 합쳐서 리스트에 저장한다.