악곱 == 악성곱슬

Simulation

---

이 문제는 순열과 조합 문제같지만,,, 전혀 성격이 다른 문제다.

그냥 규칙을 파악해서 구현피지컬이 필요한 문제다.

물론 높은 난이도는 아니나 까다롭게 실수할 가능성이 높은 문제다.

알고리즘은, 뒤 부터 앞으로 순회하며 더 큰 숫자가 나오면 킵하고 다시 뒤로 돌아가며 해당 수보다 큰 숫자중 가장 작은 숫자와 위치를 바꾸고 뒤에 있는 배열을 정렬하여 출력하면 된다.

구현

---

import sys

def solution(n):
    idx = 0
    flag = False
    for i in range(n-1, 0, -1):
        if seq[i] > seq[i-1]:
            idx = i-1
            flag = True
            break
    if not flag:
        return -1
    idx2 = 0
    tmp = 10001
    for i in range(idx, n):
        if seq[idx] < seq[i] < tmp:
            tmp = seq[i]
            idx2 = i
    seq[idx], seq[idx2] = seq[idx2], seq[idx]
    answer = " ".join(map(str, seq[:idx+1]))
    answer += " "
    answer += " ".join(map(str, sorted(seq[idx+1:])))
    return answer.strip()

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    seq = list(map(int, sys.stdin.readline().rstrip().split()))
    print(solution(N))