백준 알고리즘 10973번 (이전 순열)

이전 순열 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

3259

2072

1773

66.629%

문제

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

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

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

 

예제입력	예제출력
4 1 2 3 4	-1

 

예제입력	예제출력
5 5 4 3 2 1	5 4 3 1 2

 

[ 문제풀이 ]

 

 

[ 문제설명 ]

 

위의 문제는 순열로 표현가능한 모든 경우의 수 중 입력된 값 이전의 경우의 수를 찾는 문제이다. 보통 bfs는 모든 경우의 수를 탐색하여 결과를 찾는 방법이지만 위의 값은 사전식으로 정렬이 된다는 전제조건이 있어 전체탐색이 필요하지는 않다. 아래와 같은 절차로 확인이 가능하다. 

 

Step 별로 설명하겠습니다. TestCase는 아래의 값입니다.

- n=5

- 1 2 5 3 4

 

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 -> TestCase로 입력받은 순열

1 2 5 4 3

.... 이하 생략

 

 

1. 찾고자하는 순열 (TestCase로 입력된 순열)

 

2. 마지막 index 부터 loop 시작

    - for(int i=n-1; i>=1; i--)

 

3. 좌측 Index 값과 우측 Index값을 비교하며, 좌측 Index값이 더 크면 추가 로직 수행 (좌측 > 우측)

    - 좌측 > 우측의 경우는 Index=2의 값인 5와 Index=3의 값인 3이 체크되는 조건이다. 

    - 아래 부터는 좌측 Index를 source라고 하겠으며, 우측 Index를 target이라 하겠다.

 

4. 마지막 Index부터 target Index까지 loop 재시작 (이중 반복문)

    - 첫번째 loop의 증가변수인 i가 target index 이다.

    - for(int j=n-1; j>=i; i--)

 

5. source Index값과 step4의 loop Index값을 비교하여 값 찾기 (source Index > loop Index)

    - source Index = 5, loop index의 조건에 부합하는 것은 마지막 index값인 "4" 이다.

 

6. source Index <-> loop Index, 2개의 값을 swap 한다.

    - "5" <-> "4" swap -> "1 2 4 3 5" 로 변경이 된다.

 

7. 마지막으로 source Index의 우측 index 부터 마지막 index까지 revers 시켜준다.

    - "1 2 4 3 5" -> "1 2 4 5 3"

 

주어진 사전순으로 정렬된 순열에서 이전 경우의 수를 구할 수 있다. 전체 모든 순열을 구하여 주어진 값과 비교를 하는 방법보다 훨씬 시간복잡도가 적어진다. 하지만 위의 사전정렬 방법에 대해 공식으로 확인하여 로직화 하는게 많이 어려웠다.

 

알고리즘 문제풀이 소스는 깃헙에 모을예정입니다. (필요하시다면 fork 하셔도 괜찮습니다.)

GitHub -> https://github.com/sksggg123/algorithm

sksggg123/algorithm