최대상금.cpp

#include<iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
        // cin 버퍼 지우기?
        cin.ignore();
    
		vector<int> nums;
        while(true){
            char x;
            scanf("%1c", &x);

            if(x == ' ')
                break;
            
            nums.push_back(x - '0');
        }
        char temp;
        int totalChange = 0;
        scanf("%1c", &temp);
        totalChange = temp - '0';

        cout << "input finish" << '\n';
        for(int i=0; i<nums.size(); i++){
            cout << nums[i] << ' ';
        }
        cout << '\n';

        // solution
        int i = 0;  
        int cnt = 0;
        //for(int i=0; i<cnt; i++){
        while(true){
            // 더 이상 교체 불가
            if(cnt == totalChange)
                break;


            // 앞쪽 값을 담을 stack
            stack<int> front;
            // 뒤쪽 값을 담을 queue
            queue<int> back;

            //
            // 교환횟수: nums.size() -1 까지
            //
            if(i < nums.size()-1){
                int nowIdx = i;
                front.push(nowIdx);

                /// 교체 후보 구하기 /// 
                int maxValue = -1;
                int maxIdx = -1;
                //int maxSame = 0;
                for(int j = nums.size()-1; j > nowIdx; j--){
                    // 더 작은 수라면 교환의 후보가 아니다.
                    if(nums[j] < nums[nowIdx])
                        continue;

                    if(maxValue < nums[j]){
                        maxValue = nums[j];
                        maxIdx = j;
                        //maxSame = 0;

                        // back 비우고 삽입
                        if(back.empty())
                            back.push(maxIdx);
                        else{
                            // 먼저 비우기
                            while(!back.empty())
                                back.pop();
                            // 다 비우면 삽입
                            back.push(maxIdx);
                        }
                    }
                    // 동점 파악
                    else if(maxValue == nums[j]){
                        back.push(j);
                    }
                }

                // 교체 후보를 구했다면 
                if(back.size() >= 1){
                    // 교체 후보가 1일때
                    if(back.size() == 1){
                        // 그냥 교체
                        int frontIdx = front.top(); front.pop();
                        int backIdx = back.front(); back.pop();

                        int temp = nums[frontIdx];
                        nums[frontIdx] = nums[backIdx];
                        nums[backIdx] = temp;
                        i++;
                        cnt++;
                    }
                    // 교체 후보가 1보다 클때
                    else if(back.size() > 1){

                        // front 후보들 고르기 (내림차순에 해당하는 것들)
                        // 횟수는 최대 total - cnt -1 만큼
                        int tempCnt = 0;
                        for(int t = nowIdx+1; t < nums.size(); t++){
                            if(nums[nowIdx] > nums[t]){
                                front.push(t);
                                tempCnt++;

                                // 라스트 인덱스 갱신
                                i = t+1;

                                if(tempCnt == totalChange - cnt - 1)
                                    break;
                            }
                            
                        }

                        // 처리
                        while(true){
                            int frontIdx = front.top(); front.pop();
                            int backIdx = back.front(); back.pop();

                            int temp = nums[frontIdx];
                            nums[frontIdx] = nums[backIdx];
                            nums[backIdx] = temp;

                            cnt++;
                        }
                    }
                }
                else{
                    // 교체 후보를 구하지 못하였다면 skip 
                    i++;
                }
            }
            //
            //
            //
            else{ // 넘어가면

            }
        }


        int answer = 0;
        for(int i=0; i < nums.size(); i++){
            answer += nums[i]*pow(10, nums.size()-1-i);
        }

        cout << "#" << test_case << " " << answer << '\n';

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}