[백준] 1464번 뒤집기3 - python

문제 출처

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

1464번: 뒤집기 3

 

 

문제 풀이 및 코드

 

해당 문제는 뒤집기 정렬에 관한 문제이다. 0~i번째까지만 뒤집기가 가능하다.

 

필자는 재귀를 이용하여 접근했다. 만약 가장 작은 알파벳이 뒤에 존재한다면, 앞에서 뒤집기를 하는 과정들이 무의미하다고 생각했고 가장 앞으로 오는 알파벳을 먼저 탐색했다. 따라서 가장 작은 알파벳을 찾되, 중복이라면 가장 뒤에 있는 값을 찾고자 했다. 해당 값을 m, index를 i라고 한다면 다음과 같은 식을 생각할 수 있다.

 

뒤집기 정렬[:] = m + 뒤집기 정렬[:i] + [i+1:] 

 

i 이후의 값들은 뒤집기 정렬이 필요하지 않다. 이유는 m이 가장 작기에 그 뒤에서 뒤집기를 하게 된다면 이는 최소값이 아니게 된다. 또한 i까지 뒤집기 정렬을 한다면 i번째 값인 m이 맨앞으로 가게 된다. 물론 [:i]의 값들도 뒤집어 지지만, 0 ~ m-1까지 뒤집기를 해주어야 하는 경우가 있을 것이다. 따라서 0 ~ i까지 뒤집기 정렬을 해주어야 한다. 작성된 코드는 다음과 같다.