[백준 10973] - 이전 순열(구현) C++

문제

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

10973번: 이전 순열

접근방법

prev_permutation의 동작 원리를 묻는 문제였다.

C++에서는 prev_permutation 함수가 있어서 쉽게 풀 수 있지만, 직접 구현해보기로 했다.

 

풀이 과정은 다음과 같다.

1. 뒤에서부터 탐색하며 바로 앞의 원소가 자신보다 큰 케이스를 찾는다.

2. 그런 원소가 존재한다면 그 원소를 기준으로 뒤에서 그 원소보다 작은 수 중 가장 큰 수와 swap한다.

3. 해당 원소가 원래 위치해있던 인덱스 뒤로 모두 내림차순 정렬한다.

 

코드

직접 구현한 코드 :

#include <iostream>
#include <vector>
#include <cstring> //for memory() function
#include <algorithm>
#include <string>
using namespace std;

int main() {

    int n;
    cin >> n;
    vector<int> sunyul(n);
    for (int i=0;i<n;i++) {
        cin >> sunyul[i];
    }
    int changed = -1;
    for (int i=n-1;i>0 && changed == -1;i--) {
        int j = i;
        while(sunyul[i-1] > sunyul[j] && j < n) {
            changed = i;
            j++;
        } 
        j--;
        swap(sunyul[j], sunyul[i-1]);
    }
    if (changed == -1) cout << -1;
    else {
        sort(sunyul.begin() + changed, sunyul.end(), greater<>());
        for (int i=0;i<n;i++) cout << sunyul[i] << " ";
    }
    return 0;
}

 

prev_permutation 사용 코드 : 

int main() {

    int n;
    cin >> n;
    vector<int> sunyul(n);
    for (int i=0;i<n;i++) {
        cin >> sunyul[i];
    }
    if (prev_permutation(sunyul.begin(), sunyul.end())) for (int i=0;i < sunyul.size();i++) cout << sunyul[i] << " ";
    else cout << -1;
    cout << endl;
    
    return 0;
}

개선할 점

직접 구현한 코드에서 1,2번은 직접 생각해내야 하는 작업이었다. 3번은 sort함수를 활용해 해결할 수 있었다.

하지만 중간에서 sort를 시작하는 방법을 잘 몰라서 헤멨다.

 

알아내는 과정에서 배운 것이 있다. vector의 포인터 사용과 관련해서 내가 잘 모르고 있던 부분이었다. 

 

일단 vector를 sort를 하는 방법을 두 가지로 나눠보자면, 다음 두 개의 코드 모두 sort를 할 수 있다.

sort(sunyul.begin() + changed, sunyul.end(), greater<>());

sort(&sunyul[0] + changed, &sunyul[0] + n, greater<>());

 

sort에 필요한 건 역시 시작주소와 끝나는 점의 주소다. 나는 &sunyul로 벡터의 첫 주소를 접근하려고 했으나 계속 실패했다.

 

vector의 첫주소는 sunyul도 아니고 &sunyul도 아니다. &sunyul[0]이다.

vector는 일종의 class다. 시작점의 주소가 원소의 시작점을 의미하지 않는다. 

따라서 sunyul.begin()과 &sunyul[0]는 같다고 볼 수 있다.

 

나는 또 오해하고 있었던 점이 sunyul.begin()이 iterator라고 하길래, 주소가 아닌 줄 알았다.

 

이렇게 새로운 걸 또 배워간다. C++ 기본기가 많이 부족함을 느낀다.