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

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

1251번: 단어 나누기

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 구현
 - 문자열
 - 브루트포스 알고리즘
 - 정렬

문제

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

---

처음에는 반복문을 돌리지 않고 최대한 빠르게 처리하기 위해

문자열에서 가장 작은 글자를 찾아 거기부터 잘라서 뒤집어주는 식으로 했었다.

 

import sys
import math
input = sys.stdin.readline

s = input().rstrip()
arr1 = s[:-2]
first_min = min(arr1)
first_index = arr1.index(first_min)
while True:
    if first_index+1 < len(arr1):
        if arr1[first_index] == arr1[first_index+1]:
            first_index += 1
        else:
            break
    else:
        break
arr1 = s[:first_index+1]

arr2 = s[first_index+1:-1]
second_min = min(arr2)
second_index = arr2.index(second_min)
while True:
    if second_index+1 < len(arr2):
        if arr2[second_index] == arr2[second_index+1]:
            second_index += 1
        else:
            break
    else:
        break
arr2 = arr2[:second_index+1]

arr3 = s[len(arr1) + len(arr2): ]

r1 = reversed(arr1)
r2 = reversed(arr2)
r3 = reversed(arr3)
result = ''.join(r1) + ''.join(r2) + ''.join(r3)
print(result)

결과는 틀렸습니다. 였다.

 

cabadd

내 결과 : acabdd
정답 : abacdd

첫 번째 a부터 잘려서 acab가 되었다.

---

 

그래서 위의 방법을 버리고

 

그냥 반복문으로 돌리는 방법을 채택했다.

 

import sys
input = sys.stdin.readline

s = input().rstrip()
arr1 = ""
arr2 = ""
arr3 = ""

result = ""
for i in range(0, len(s)-2):
    arr1 = s[:i+1]
    for j in range(i+1, len(s)-1):
        arr2 = s[i+1:j+1]
        arr3 = s[j+1:]
        
        r1 = reversed(arr1)
        r2 = reversed(arr2)
        r3 = reversed(arr3)
        
        tmp = ''.join(r1) + ''.join(r2) + ''.join(r3)
        if result > tmp or result == "":
            result = tmp
        
print(result)

첫 번째 결과를 result에 저장하기 위해

 

if문 안에 result == "" 조건을 넣어 주었다.

 

만약 처음부터 result = s 로 지정하였으면

 

abcdefg

내 결과 : abcdefg
정답 : abgfedc

반드시 한 번은 나눠서 뒤집어줘야 하기 때문에 저러한 조건을 넣어 주었다.

 

위의 코드의 결과는 성공

 

---

반례 모음

 

mobitel

bometil

--------------------------

abc

abc

--------------------------

abbc

abbc

--------------------------

aabc

aabc

--------------------------

zyaa

yzaa

--------------------------

cabadd

abacdd

--------------------------

abcdefg

abgfedc

--------------------------

zzzzaaaa

aazzzzaa

--------------------------

zzaa

zaza

--------------------------

azzazza

aazzazz