[BOJ/백준] 10972 다음 순열

● [문제번호 10972] 다음 순열

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

10972번: 다음 순열

 

● 알아야 할 것

: NULL

 

● 풀이 과정

: 브루트 포스로 구현해보려고 고민했지만,

재귀를 이용하면 깊이가 10,000 이나 되어서 '메모리 초과' 가 나올 것 같고,

반복문을 이용하자니 N 값을 몰라 수월한 방법이 떠오르지 않아서,

수열에 대해 분석을 해보았다.

 

: 기존 수열에서 다음 수열로 어떻게 바뀌는 지 분석하니,

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

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

 

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

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

 

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

 

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

 

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

{왼쪽 원소} < {오른쪽 원소} 인 경우

 

● 주의 할 것

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

 

● 참고 할 것

: C++ STL에는 다음 순열을 찾는 함수가 있다.

https://mjmjmj98.tistory.com/38

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

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

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);
            
            // 마지막 순열이 아니라는 신호
            flag = 1;
            break;
        }
    }
    
    // 마지막 순열인 경우
    if(flag == 0)
        cout << -1;
    // 마지막 순열이 아닌 경우
    else
        for(int n = 0; n < N; n++)
            cout << num[n] << " ";
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

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];
    
    // STL 함수 이용
    // 다음 순열이 존재하면
    // 해당 배열을 다음 순열로 만들고 TRUE 반환
    if(next_permutation(num, num + N))
        for(int i = 0; i < N; i++)
            cout << num[i] << " ";
    else
        cout << -1;
    
    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