[백준 9440번] [그리디] 숫자 더하기

사실 잘 생각해보면, 작은 숫자들을 순차적으로 뽑아주면 된다.

우선순위 큐를 활용해주어도 괜찮고, 전체 쿼리의 업데이트가 없으므로 배열을 정렬해줘서 하나씩 탐색하는 방식으로 처리해주어도 무방하다.

 

다만 0이 여러개 등장할 수 있는 지점만 조심해주면 된다.

(맨 앞자리가 0이 될 수 없으므로 2번째 자리 이후부터 0을 배치하면 된다. 즉 첫 자리는 0이 아닌 숫자를 무조건 배치하고 0을 고려해주면 된다.)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    while(true){
        int n;
        cin >> n;
        vector<int> data;
        if(n == 0) break;
        else{
            int zero_count = 0;
            for(int i = 0; i < n; i++){
                int temp;
                cin >> temp;
                if(temp == 0) zero_count++;
                else data.push_back(temp);
            }
            sort(data.begin(), data.end());

            vector<int> first;
            vector<int> second;
            int cur_index = 2;
            
            first.push_back(data[0]);
            second.push_back(data[1]);

            while(zero_count > 0){
                first.push_back(0);
                zero_count -= 1;
                if(zero_count > 0){
                    second.push_back(0);
                    zero_count -= 1;
                }
                else{
                    if(cur_index < data.size()){
                        second.push_back(data[cur_index++]);
                    }
                }
            }

            while(cur_index < data.size()){
                first.push_back(data[cur_index++]);
                if(cur_index < data.size()){
                    second.push_back(data[cur_index++]);
                }
            }

            int result = 0;

            for(int i = 0; i < first.size(); i++){
                result += first[i] * pow(10, first.size() - i - 1);
            }
            for(int j = 0; j < second.size(); j++){
                result += second[j] * pow(10, second.size() - j - 1);
            }

            cout << result << "\n";
        }
    }
    return 0;
}