프로그래머스 : 가장 큰 수 (C++, Lv.2,정렬)

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

필자는 numbers안 숫자들을 모두 같은 자릿수로 바꿔 비교한 다음에 정렬해 넣으려고 했으나 결국 실패하고 말았다ㅜ

 

그래서 블로그를 찾아보니 문자열로도 충분히 합친 문자열의 대소를 분류할 수 있다는 것을 알게 되었다.

algorithm 헤더 내의 sort 에 대해 좀 더 공부해볼 생각이다.

https://ongveloper.tistory.com/66

프로그래머스 가장 큰 수 c++ (정렬)

 

 

 

소스코드 (참고함)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//두 문자열을 인자로 받아 붙일 수 있는 경우를 비교
bool cmp (string a, string b) {
    return a+b> b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;
    //numbers내의 숫자들을 문자열로 변환해 벡터에 저장
    for(int n : numbers) {
        v.push_back(to_string(n));
    }
    //퀵정렬 (algorithm 헤더)
    sort(v.begin(), v.end(), cmp);
    
    if(v[0].compare("0")==0) return "0";
    // 문자열 이어 붙이기
    for(string s : v) {
        answer += s;
    }
    return answer;
}

---

실패코드

시간 초과 꽤 킹받는다...

이거 전에도 계속 실수하긴 했다 그래도 다시 생각해보고 새롭게 푼건데 시간초과 뜨니 속상...

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<pair<int,int>> v;
    pair<int, int> p;
    // i : numbers의 인덱스
    for(int i = 0; i< numbers.size(); i++) {
        
        int mod_num = numbers[i];
        if(mod_num == 0) v.push_back(make_pair(mod_num, i));
        int n = mod_num % 10;
        while(mod_num < 10000) mod_num = mod_num * 10 + n;
        v.push_back(make_pair(mod_num, i));
    }
    
    sort(v.begin(), v.end());
    
    for(auto a : v) {
        answer = to_string(numbers[a.second]) + answer;
    }
    return answer;
}

---

실패 코드2

이전 코드에서 if(mod_num == 0)일 때 푸시하고 for문을 나왔어야 했는데 그걸 빼먹었어 시간이 오류가 난 것 같다.

근데 그래도 틀렸다...

생각해보니 numbers == 10일 때랑 numbers = 1000 우선순위가 동일하게 처리되는게 문제였다...

결국 내가 생각한 로직은 완전히 틀렸단 소리다....

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<pair<int,int>> v;
    pair<int, int> p;
    // i : numbers의 인덱스
    for(int i = 0; i< numbers.size(); i++) {
        
        int mod_num = numbers[i];
        if(mod_num == 0) {
            v.push_back(make_pair(mod_num, i));
            continue;
        }
        int n = mod_num % 10;
        while(mod_num < 1000) mod_num = mod_num * 10 + n;
        v.push_back(make_pair(mod_num, i));
    }
    
    sort(v.begin(), v.end());
    
    for(auto a : v) {
        answer = to_string(numbers[a.second]) + answer;
    }
    return answer;
}