BOJ 10973. 이전 순열

🙇‍♀️[Silver III] 이전 순열 - 10973

문제 링크

성능 요약

메모리: 2180 KB, 시간: 0 ms

분류

조합론, 구현, 수학

제출 일자

2024년 6월 24일 19:09:09

문제 설명

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을 출력한다.

🚀풀이

이전 순열을 구하기 위한 공식이 있었다.

그걸 그대로 구현하면 된다.

이전 순열을 구하는 공식은 다음과 같다.

1. 뒤에서부터 첫 번째 감소하는 요소를 찾음
2. perm[i-1]보다 작은 요소를 뒤에서부터 찾음
3. i-1 위치의 요소와 j 위치의 요소를 교환
4. i 위치부터 끝까지의 요소를 역순으로 바꿈

이걸 함수로 표현했다.

// 이전 순열을 찾는 함수
bool PrevPermutation(vector<int>& perm) 
{
    int n = perm.size();
    int i = n - 1;

    // Step 1: 뒤에서부터 첫 번째 감소하는 요소를 찾음
    while (i > 0 && perm[i - 1] <= perm[i]) 
    {
        i--;
    }

    if (i == 0) 
    {
        return false; // 이전 순열이 없음 (가장 첫 번째 순열)
    }

    // Step 2: perm[i-1]보다 작은 요소를 뒤에서부터 찾음
    int j = n - 1;
    while (perm[j] >= perm[i - 1]) 
    {
        j--;
    }

    // Step 3: i-1 위치의 요소와 j 위치의 요소를 교환
    swap(perm[i - 1], perm[j]);

    // Step 4: i 위치부터 끝까지의 요소를 역순으로 바꿈
    reverse(perm.begin() + i, perm.end());

    return true;
}

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

// 이전 순열을 찾는 함수
bool PrevPermutation(vector<int>& perm) 
{
    int n = perm.size();
    int i = n - 1;

    // Step 1: 뒤에서부터 첫 번째 감소하는 요소를 찾음
    while (i > 0 && perm[i - 1] <= perm[i]) 
    {
        i--;
    }

    if (i == 0) 
    {
        return false; // 이전 순열이 없음 (가장 첫 번째 순열)
    }

    // Step 2: perm[i-1]보다 작은 요소를 뒤에서부터 찾음
    int j = n - 1;
    while (perm[j] >= perm[i - 1]) 
    {
        j--;
    }

    // Step 3: i-1 위치의 요소와 j 위치의 요소를 교환
    swap(perm[i - 1], perm[j]);

    // Step 4: i 위치부터 끝까지의 요소를 역순으로 바꿈
    reverse(perm.begin() + i, perm.end());

    return true;
}

void solve()
{
    int N;
    cin >> N; // 순열의 크기 입력 받기
    vector<int> perm(N);

    for (int i = 0; i < N; ++i) 
    {
        cin >> perm[i]; // 순열 입력 받기
    }

    // 이전 순열이 존재하면 출력
    if (PrevPermutation(perm)) 
    {
        for (int i = 0; i < N; ++i) 
        {
            cout << perm[i] << " ";
        }
        cout << endl;
    }
    else 
    {
        cout << -1 << endl; // 이전 순열이 없으면 -1 출력
    }

}

int main() 
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}