[알고리즘] 백준 10972

layout: post
title: "백준 10972 다음 순열"
date: 2022-03-12T00:00:00-00:00
author: sangyeop
categories: Algorithm

백준 10972 다음 순열

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

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

실패

• 모든 순열을 구해서 크기 순으로 배열에 저장한 뒤, 순차적으로 검사하여 입력된 값보다 큰 값을 출력하려고 하였으나 시간 초과 에러가 터질것 같았음

성공

• 모든 순열을 구할 필요없이, 입력된 순열에서 규칙을 찾아 swap하고 정렬해줌으로써 문제를 해결할 수 있었음

1. 순열을 뒤에서 부터 탐색한다.
   • 주어진 순열보다 바로 다음으로 큰 순열을 찾아야하므로, 일의 자리인 배열의 가장 뒤쪽부터 탐색해야함
2. arr[i-1] < arr[i] 가 성립하는 가장 큰 인덱스 i를 구한다.
   • i의 값을 -1씩 진행하면서 탐색한다.
   • 만약 i가 0이하가 될 경우 최대값임을 의미하므로 -1을 반환한다.
3. arr[i-1]과 a[i]부터 arr[arr.length-1](배열의 끝 값) 에서 arr[i-1]보다 큰 수 중에서 가장 작은 값을 찾은 뒤, arr[i-1]과 스왑한다.
4. arr[i] ~ a[arr.length-1] 의 값은 배열의 뒤에서 앞으로 증가하는 순으로 정렬되어 있음이 2번을 통해서 검증 되었으므로, i를 1씩 증가하고 arr.length-1 을 1씩 감소시키면서 arr[i] 와 arr[arr.length-1]의 값을 swap 시켜주면서 정렬한다.

이를 예제로 표현하면 다음과 같다

주어진 입력

1 8 4 7 6 5 3 2

1 8 4 7 6 5 3 2

1 8 5 7 6 4 3 2

1 8 5 2 3 4 6 7

index :0 1 2 3 4 5 6 7
input :1 8 4 7 6 5 3 2

• 1, 2

  • 뒤에서 탐색했을때 숫자 4에서 처음으로 arr[i-1] < arr[i]가 성립함
  • i = 3

• 3

  • 7 6 5 3 2 중에서 4보다 큰 값중 가장 작은 값을 찾는다

  • 마찬가지로 뒤에서부터(arr[arr.length-1]) 탐색해서 처음으로 arr[i-1]` 보다 큰 값이 있는 인덱스를 저장한다

  • j = 5

  • arr[i-1] 과 arr[j] 값을 swap 한다.

  • 1 8 5 7 6 4 3 2

• 4

  • 7 6 4 3 2 // arr[i] ~ arr[j]

  • 위 범위의 숫자들은 내림차순으로 정렬되어 있으므로 이를 오름차순으로 바꿔준다

    • arr[i]와 arr[j]를 swap 하면서 i가 j보다 작을 동안에 대해서 i++ , j--를 반복문을 통해 수행한다`