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

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

Created
2022/06/30
Tags
Algorithm
Python
 
 
2022-06-30 @이영훈
 
 
최종적으로 정리된 버전
Python
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에서 string 비교가 min 내장 함수로 되는지 몰랐음
  • 글자를 뒤집기 위해서 reversed로 map 객체를 만들고 join해서 구현 (이해가 더 쉽긴하다. pythonic 하진 않음)
Python
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)