[백준/C++]1083번_소트

이수진·2022년 7월 29일
0
post-custom-banner

문제는 다음과 같습니다.

일단 문제를 요약하면 다음과 같습니다.

소트한 결과가 사전수능로 가장 뒷서야 하므로
제한된 횟수 S번 내에 첫번째 자리부터 ~ (이후 자리까지) 가장 뒷 번째 수를 가져와야합니다.
⭐️(제한된 횟수 내에서 가져올 수 있는 가장 큰 수 찾기)⭐️

제 전체 코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> v;
    int N, S, tmp; cin >> N;

    for(int i=0; i<N; i++){
        cin >> tmp;
        v.push_back(tmp);
    }
    cin >> S;

    vector<int> vv = v;
    sort(vv.begin(), vv.end());


    for(int i=0; i<v.size() && S>0; i++){
        if(v[i] == vv[vv.size()-i]) continue; // 내림차순 정렬이 된 것

        int j, cnt=S, max_el = v[i], max_idx = i;

        for(j=i+1; j<v.size() && cnt>0; j++, cnt--){ // 대체 원소 찾는 과정
            if(max_el < v[j]){
                max_el = v[j];
                max_idx = j;
            }
        }

        S -= (max_idx - i);
        for(; max_idx>=i+1; max_idx--) swap(v[max_idx], v[max_idx-1]); // swap

        if(S==0) break;
    }


    for(int i=0; i<v.size(); i++) cout << v[i] << " ";
    return 0;
}

문제 원리는 쉽지만,
특정 알고리즘 유형이 아닌, 시뮬레이션이나 구현, 그리디와 같은 문제가 좀 까다로운 것 같습니다..

profile
꾸준히, 열심히, 그리고 잘하자
post-custom-banner

0개의 댓글