[BOJ/백준] 10973 이전 순열

● [문제번호 10973] 이전 순열

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

10973번: 이전 순열

 

● 알아야 할 것

: NULL

 

● 풀이 과정

: 다음 순열 문제에서 부등호만 잘 바꿔주면 된다.

 

: 다음 순열 문제와 같은 원리로

1. 기존 수열의 맨 오른쪽부터 하나씩

{왼쪽 원소} > {오른쪽 원소} 인지 검사한다.

 

2. 조건에 맞으면 그 왼쪽 원소(기준 : 값교환해도 index는 그대로)를 중심으로 오른쪽에 존재하는 원소들 중에서

'기준보다 작은 값 중 가장 큰 값' 을 찾으면 된다.

 

3. 그렇게 찾은 값을 기준의 값과 교환한다.

 

4. 다시 기준을 중심으로 오른쪽 원소들을 내림차순 하면 된다.

기본 sort함수는 오름차순이므로 내림차순으로 만들기 위한 desc함수를 만든다.

 

아래 사진은 1, 2, 3, 4의 예시이다.

{왼쪽 원소} > {오른쪽 원소}

 

● 주의 할 것

: 기준의 값을 교환하고 다시 기준의 오른쪽 원소들을 정렬하는 작업 중에 index에 주의한다.

 

: 기본 sort는 오름차순으로 정렬하므로

내림차순으로 만들기 위한 desc함수를 만든다.

 

● 참고 할 것

: 10972 다음 순열

https://pirateturtle.tistory.com/237

 

: sort함수를 내림차순으로 만드는 방법

https://coding-factory.tistory.com/595

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 입력될 순열
int num[10000] = {0, };
int N;

bool desc(int a, int b)
{
    return a > b;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 순열 입력
    for(int n = 0; n < N; n++)
        cin >> num[n];
    
    // flag : 첫 순열인지 확인을 위한 변수
    int flag = 0;
    // 입력된 순열의 마지막부터 검사
    for(int i = N - 1; i > 0; i--)
    {
        // 왼쪽 원소(기준) > 오른쪽 원소
        if(num[i - 1] > num[i])
        {
            // index : 교환할 원소의 인덱스 (i는 최대의 index를 찾기 위함)
            int index = i;
            // 기준 원소보다 오른쪽에 있으면서 
            for(int j = N - 1; j >= i; j--)
            {
                // 기준 원소보다 작으면서 + 제일 큰 원소
                if(num[i - 1] > num[j] && num[j] > num[index])
                    index = j;
            }
            
            // 교환 작업
            int temp = num[index];
            num[index] = num[i - 1];
            num[i - 1] = temp;
            
            // 기준 원소 우측 내림차순으로 정렬
            sort(num + i, num + N, desc);
            
            // 첫 순열이 아니라는 신호
            flag = 1;
            break;
        }
    }
    
    // 첫 순열인 경우
    if(flag == 0)
        cout << -1;
    // 첫 순열이 아닌 경우
    else
        for(int n = 0; n < N; n++)
            cout << num[n] << " ";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 - 순열] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10972	다음 순열	https://pirateturtle.tistory.com/237
2	10973	이전 순열	https://pirateturtle.tistory.com/238
3	10974	모든 순열	https://pirateturtle.tistory.com/239
4	10819	차이를 최대로	https://pirateturtle.tistory.com/240
5	10971	외판원 순회 2	https://pirateturtle.tistory.com/241
6	6603	로또	https://pirateturtle.tistory.com/242