[python] 백준 1464 뒤집기 3

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

1464번: 뒤집기 3

문제 해결

• 간단해 보이지만 생각보다 간단하지 않은 문제
• 무조건 맨 왼쪽 문자부터 뒤집어야 한다는 규칙이 있다.
• 한 문자씩 왼쪽에서 오른쪽으로 볼 때 맨 뒤 혹은 맨 앞에 올 문자를 업데이트 한다고 보는 것이 편하다.
• 맨 앞에 올 수 있는 문자가 오면 그 앞에서 문자열 양 사이드 중 사전순으로 빠른 글자를 맨뒤로 오도록 뒤집은 다음 맨 앞에 올 수 있는 문자를 합하여 뒤집으면 된다.
• 사실 구현이 쉽지 않았고 다른 분들의 풀이를 참고하였다. (간단하게 푸신 분들 리스페트...!)

 

CODE

import sys
input = sys.stdin.readline
s = list(input().rstrip())
n = len(s)

def Reverse(left,right,iterable):
    while left<right-1:
        temp = iterable[right-1]
        iterable[right-1] = iterable[left]
        iterable[left] = temp
        left += 1
        right -= 1
    return iterable

for i in range(0,n-1):
    end = i + 1
    if s[i] > s[end] and s[end] <= s[0]: # i는 0이 될 수도 있다. 그래서 CBA와 같이 한번만 뒤집어도 되는 문자열도 다음과 같은 알고리즘에서 정답이 나온다.
        Reverse(0,end,s)
        if s[i] >= s[end]:
            Reverse(0,end+1,s)
for x in s:
    print(x, end='')