[백준-Python] 단어 나누기 : 1251번

🥈 Silver5

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

 

 

import sys
from itertools import combinations

input = sys.stdin.readline
word = list(input().strip())
word_length = len(word)

result = set()

for i in range(1, word_length - 1):
    for j in range(i+1, word_length):
        first = word[:i]
        sec = word[i:j]
        thrid = word[j:]

        # reverse
        first.reverse()
        sec.reverse()
        thrid.reverse()

        # 합치기
        result.add("".join(first+sec+thrid))
print(sorted(result)[0])

# 31120	44

이 문제는 길이가 1이상으로 3부분으로 나누고, 뒤집어서 합치고 사전순 정렬로 가장 첫번째 요소만 찾으면 되기 때문에,

3부분으로 단어를 나누는 부분을 제외하곤 어렵지 않은 문제다.

 

처음에 아무생각 없이 1이상으로 나누는것을 combinations같은 조합을 사용해야겠다고 생각했는데, 조합은 1개씩 뽑아서 만들어주기 때문에 사용할 수 없었다. 

3가지의 경우로 나누기 위해 이중 for문을 사용해, i 포인터와 j 포인터로, j를 i다음 요소부터 맨 마지막 요소를 제외한 (i+1, word_length) 범위내에서 경우를 만들어 나간다. 

first = i포인터가 가리키는 곳까지

sec=i 포인터 이후부터 j포인터가 가리키는곳 까지

thrid=j포인터 이후 나머지

 

 

별로 어려워보이지 않는데 이 3부분으로 나누는게 어려웠다..😢