[백준] 단어 나누기(python)

백준, 단어 나누기

1251번: 단어 나누기

TL;DR

• 문자열(string)
• 완전 탐색(brute force)

문제 요약

1. 알파벳 소문자로 이루어진 단어를 세 개의 작은 단어들로 나누어 합쳤을 때 사전 순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하라.
2. 나눠진 단어들은 적어도 길이가 1 이상이여야 한다.

 

- 입력 받은 문자열을 3개로 나누고 나눈 작은 문자열을 뒤집어서 다시 합쳤을 때 가장 작은 문자열이 오도록 하면 된다.

- 입력 문자열의 길이가 3 이상 50 이하로 주어졌기 때문에 완전 탐색을 사용해 모든 경우의 수를 찾아보는 방식을 사용하면 문제를 해결할 수 있다.

입출력 형태

입출력 예시

 

예시 1 :: 주어진 단어 mobitel을 세 부분으로 나눠서 다시 조합한 문자열 중 가장 작은 경우인 bometil을 출력하였다.

풀이

완전 탐색으로 문제를 해결하기 위해선 문자열을 나눌 수 있는 모든 경우의 수로 만들어보는 것이다.

- 가장 첫 번째로 나눌 수 있는 방법은 가장 첫 번째 문자와 두 번째 문자, 그리고 나머지 부분으로 나누는 것이다. 이를 코드로 작성하면 `word[0:1], word[1:2], word[2:]`과 같이 작성할 수 있다.

   - 이 때, 예시 1에 대해서 적용하면 m, o, bitel로 나눌 수 있다.

- 다음으로 만들 수 있는 경우는 코드로 `word[0:1], word[1:3], word[3:]`과 같이 작성할 수 있다.

    - 이 때, 예시 1에 대해서 적용하면 m, ob, itel으로 나눌 수 있다.

import sys
INPUT = sys.stdin.readline

word = INPUT()[:-1]
words = []
for i in range(1, len(word) - 1):
  for j in range(i + 1, len(word)):
    first = word[:i][::-1]
    second = word[i:j][::-1]
    third = word[j:][::-1]
    words.append(first + second + third)
words.sort()
print(words[0])

 

여기서 규칙을 찾을 수 있고, 이를 코드로 구현한 부분이 2중 반복문 안에 작성되어 있다.

- 나누는 문자열의 인덱스를 조정해서 슬라이싱해서 나누어주면 된다. 조합해서 만든 문자들을 리스트에 담아둔다.

문제에서 원하는 답은 사전 상 가장 앞에 오는 문자열이므로 정렬을 한 뒤 0번째 인덱스 값을 출력하면 답을 얻을 수 있다.