[백준] 다음 순열_10972

다음 순열_10972

코드

# 2023-02-26 21:55:57
# https://www.acmicpc.net/problem/10972

import sys
input = sys.stdin.readline

n = int(input())
m = list(map(int, input().split()))

for i in range(n-1, 0, -1) :
    if m[i-1] < m[i] : # 앞 < 뒤
        for j in range(n-1, 0, -1) :
            if m[i-1] < m[j] :
                m[i-1], m[j] = m[j], m[i-1]
                m = m[:i] + sorted(m[i:])
                print(*m)
                exit()  # 코드 종료

print(-1)  # 코드 종료 발생 X -> -1 출력

---

풀이노트

N = 5인 경우 사전순으로 나열해보자.
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
...

1 2 3 4 5의 경우 4와 5를 교체한다.
1 2 3 5 4의 경우 3과 4를 교체하고, 원래 3이 있던 자리를 기준으로 뒤의 숫자를 정렬한다.
1 2 4 3 5의 경우 3과 5를 교체한다.
1 2 4 5 3의 경우 4와 5를 교체하고, 원래 4가 있던 자리를 기준으로 뒤의 숫자를 정렬한다.

---

이 원리를 확장해보자.

• 반복문을 숫자 리스트의 뒤에서부터 탐색하는 것이 좋다.
  • for i in range(n-1, 0, -1)
• 앞(i-1) < 뒤(i) 인 경우, 앞(i-1)과 뒤의 숫자들 중 앞(i-1)보다 크지만 가장 작은 수와 교체해야 한다.
  • 예: 1 3 5 4 2의 경우 3과 5 4 2 중에 교체해야 한다. 이 때 (i-1)번째 뒤에 있는 숫자들은 역순으로 정렬된다. (i-1) 이후에 있는 숫자 중에서 3보다 큰 숫자들 중 가장 작은 숫자는 4이다. 따라서 3과 4를 교체한다.
  • for j in range(n-1, 0, -1) :
    • if m[i-1] < m[j] :
      • m[i-1], m[j] = m[j], m[i-1]
• 바뀐 위치는 (i-1)이다. 처음부터 (i-1)은 그대로 두고, (i-1) 이후의 숫자를 정렬한다.
  • m = m[:i] + sorted(m[i:])

---

팁

• print(*s)
  • 1차원 리스트 앞에 *을 붙이면 공백과 함께 각 원소를 출력함
  • 예: 1 2 3 4 5
• exit()
  • 코드 종료
  • 값을 찾을 수 없을 때 -1을 출력하야 하는 경우 유용함
  • find_answer = True와 같은 변수를 만들지 않아도 됨
• C++에서는 next_permutation을 사용하면 쉽게 풀 수 있음

---

생각

나중에도 아이디어 생각이 떠오르지 않을 것 같다. 나중에 다시 풀어보자!
그리디 같은데 왜 완전 탐색일까?