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

2023. 7. 29. 21:42백준 & 프로그래머스

문제 출처

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

 

1464번: 뒤집기 3

세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는

www.acmicpc.net

 

 

문제 풀이 및 코드

 

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

 

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

 

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

 

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