[알고리즘] 백준 1251번 단어 나누기 python

Created

2022/06/30

Tags

Algorithm

Python

2022-06-30 @이영훈

1251번: 단어 나누기

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

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

최종적으로 정리된 버전

string = input()

# 사전순으로 가장 큰 수를 미리 입력
answer = "z" * len(string)

# 세 단어로 나누기 위해서 두 번을 자름
# 시간 복잡도: O(n^2)
for i in range(1, len(string) - 1):
    for j in range(i + 1, len(string)):
        s1 = string[:i][::-1]
        s2 = string[i:j][::-1]
        s3 = string[j:][::-1]
        new_string = s1 + s2 + s3
        answer = min(answer, new_string)  # 사전순으로 더 앞선 수를 가져옴

print(answer)
Python
복사

처음 만든 버전

•

python에서 string 비교가 min 내장 함수로 되는지 몰랐음

•

글자를 뒤집기 위해서 reversed로 map 객체를 만들고 join해서 구현 (이해가 더 쉽긴하다. pythonic 하진 않음)

string = input()

answer = "z" * len(string)

def get_alphabetic_lower_string(one, the_other):
    for i in range(len(one)):
        if ord(one[i]) < ord(the_other[i]):
            return one
        elif ord(one[i]) > ord(the_other[i]):
            return the_other
    return one

for i in range(1, len(string) - 1):
    for j in range(i + 1, len(string)):
        s1 = ''.join(reversed(string[:i]))
        s2 = ''.join(reversed(string[i:j]))
        s3 = ''.join(reversed(string[j:]))
        new_string = s1 + s2 + s3
        answer = get_alphabetic_lower_string(answer, new_string)

print(answer)
Python
복사