[ 백준 BOJ ] 1083번 - 소트 (C++)

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

 

생각 흐름

• dfs로 각 자리에서 한 번씩 교환하면서 가장 큰 수를 찾을까 하다가 무조건 시간초과임을 발견
• 이후 한 번씩 교환한 수 중에 가장 큰 수로 접근하면 될까했지만 10 20 50이고 S가 2일 때 한 번 교환이 이뤄날 때 (20 10 50), (10 50 20)일 때 (10 50 20)이 버려지게 된다. 즉, (50 10 20)이 안 된다.
• 결국 문제의 해결에서 키포인트는 큰 수가 앞으로 와야 한다는 점이다. 따라서 각 자리에서 S가 만족할 때 가장 큰 수를 가져오는 방식으로 접근하기로 했다.
  • 즉, 10 20 50이고 S가 2일 때 10의 자리에서 50이 제일 크고, 10과 50의 자리를 바꿀 때 2번만 교환이 이뤄지므로 바꿔주면 된다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v;
int S;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        v.push_back(tmp);
    }
    
    cin>>S;
    
    for(int i = 0; i<v.size(); i++){
        int maxNum = v[i];
        int maxIndex = -1;
        for(int j = i+1; j<v.size(); j++){
            if(maxNum<v[j]){
                if(j-i>S) break;
                
                maxNum = v[j];
                maxIndex = j;
            }
        }
        
        if(maxIndex != -1){
            S -= maxIndex-i;
        }
        
        for(int j = maxIndex; j>i; j--){
            int tmp = v[j-1];
            v[j-1] = v[j];
            v[j] = tmp;
        }
        
        if(S==0) break;
    }
    
    for(auto i : v){
        cout<<i<<" ";
    }
    cout<<endl;
    
    return 0;
}