알고리즘 유형 : 수학

소스 코드 (파이썬)

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = [*map(int, input().strip().split())]

# 초기 비교 쌍 idx 위치
left_init, right_init = -2, -1

# 오른쪽부터 순회하여 오름차순 쌍을 최초 발견했을 때 왼쪽 것 idx
swap_left = -1

# 오름차순 쌍이 하나라도 존재하는지 여부
is_finded = False

# 오름차순 쌍을 오른쪽부터 쭉 찾기
for step in range(N-1):
    left_idx = left_init - step
    right_idx = right_init - step

    if arr[left_idx] < arr[right_idx]:
        is_finded = True
        swap_left = left_idx
        break

if not is_finded:
    print(-1)
else:
    # swap_left보다 큰 원소를 맨 오른쪽 원소부터 순회하며 다시 찾기
    # 발견하면 그 것과 swap 후, 최초 오름차순 쌍의 오른쪽 원소 idx 자리부터 맨 오른쪽 끝까지 오름차순 정렬
    for idx in range(0, swap_left, -1):
        check_right = right_init + idx

        if arr[swap_left] < arr[check_right]:
            arr[swap_left], arr[check_right] = arr[check_right], arr[swap_left]
            arr = arr[:swap_left+1] + sorted(arr[swap_left+1:])
            break

    print(*arr)

풀이 요약

1. 주어진 순열의 맨 오른쪽부터, 인접한 두 개의 원소 쌍이 오름차순인 것을 발견할 때까지 왼쪽 방향으로 순회

2. 찾았으면, 그 쌍의 왼쪽 원소가 swap_left임. 이제 다시 순열의 맨 오른쪽부터 원소 하나씩 순회하면서, swap_left보다 큰지(오름차순) 체크하기

3. 찾았으면 그 원소와 swap_left 위치의 원소를 swap 하기

4. 처음에 찾았던 오름차순 쌍에서 오른쪽 원소 위치를 기준으로, 그 원소를 포함해서 맨 오른쪽까지를 오름차순 정렬후, 순열 맨 왼쪽부터 swap_left까지의 부분 리스트와 이어 붙이기

어려웠던 점, 배운 점

• 처음에 순열 문제인 줄 알았는데, 시간복잡도가 O(N!)인데 N이 10000까지라서 순열 문제는 아닌 것 같아서 다른 규칙이 있나 찾아봤지만 결국 못 찾고 다른 사람 풀이를 참고했다. 수학 유형 문제인 듯 하다.

• 앞으로 사전 순에 관련된 문제를 접할 때, 여기서 익힌 규칙 아이디어가 도움이 될수도 있을 듯하다.