[그리디] BOJ 16496 큰 수 만들기

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

16496번: 큰 수 만들기

 

문제 해결 알고리즘 

 

그리디하게 a + b와 b + a 중에 큰 것으로 정렬을 해준다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

bool cmp(string a, string b){
    
    if(a == b) return false;
    
    string ab = a+b;
    string ba = b+a;
    
    if(ab > ba) return true;
    else  return false;
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N; cin >> N;
    
    vector<string> v(N);
    
    int flag = 0;
    for(int i=0;i<N;i++){
        cin >> v[i];
        if(v[i] != "0") flag = 1;
    }
    
    
    if(flag == 0) cout << 0;
    else {
        
        sort(v.begin(), v.end(), cmp);
        for(int i=0;i<N;i++){
            cout << v[i];
        }
    }
    
}

 

메모

 

strict weak ordering에 맞게 cmp함수를 구성해주어야한다. 런타임 에러 나온다..

cmp 함수 구성할 때에 어설프게 비교하게 설계하지 말자..