프로그래머스 : 정렬 - 가장 큰 수

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

프로그래머스

만만하게 봤다가 오늘도 수많은 삽질끝에 해결했다^^..

생각했던 것들을 순서대로 나열하면서 어떻게 해결했는지를 설명해보려고한다!

---

1. 문장열로 정렬하기

=> 이런문제에서, 주어진 숫자들 중 값이 큰게 앞으로 간다고, 합쳤을 때 더 큰 숫자가 나온다는 보장이 없다

ex) [9, 10] => 910 (109가 아님)

c++에서는, string을 정렬하면 '사전순'으로 정렬해준다.

 

[9, 10], 오름차순

1. int로 정렬 => [9, 10]

2. string으로 정렬 => [10, 9]

이런식으로 말이다!

 

그래서 주어진 int리스트를, string으로 변경해서 그냥 sort만 해주면 된다고 생각했다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> snums;
    
    for(int i = 0; i<numbers.size(); i++){
        snums.push_back(to_string(numbers[i]));
    }
    
    sort(snums.begin(), snums.end(), greater<>{});
    
    for(int i = 0; i<snums.size(); i++){
        answer += snums[i];
    }

    return answer;
}

결과는..?!

앗.. 주어진 테스트도 통과하지 못했다.

---

2. "3" vs "30" ???

이런 경우,, c++에서는 어떻게 정렬을해줄까? => 오름차순 3, 30 순서로 정렬해준다 (30이 더 크다고 판단)

하지만 문제를 해결하기 위해서는, 3이 더 크다고 판단해서 (즉 내림차순 정렬했을 때 3, 30으로 해줘야) 더 큰 숫자를 만들 수 있다

(303 vs 330)

그래서 그냥 뒤에 0이 붙은것만 빼면 똑같은경우 정렬을 반대로 해주도록 새롭게 compare함수를 만들어주었다

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool comp(string a, string b){
    int numa = stoi(a);
    int numb = stoi(b);
    
    // a : 30, b : 3 같은 상황
    if((numa % 10 == 0 && numa % numb == 0)){
        // a : 10, b : 5 혹은 b : 2같은 상황일 수 있음
        if((numa / numb) % 10 == 0){
            return a < b;
        }
    }
    
    // a : 3, b : 30
    if((numb % 10 == 0 && numb % numa == 0)){
        // a : 5/2, b : 10 같은 상황일 수 있음
        if((numb / numa) % 10 == 0){
            return a < b;
        }
    }
    
    return a > b;
}



string solution(vector<int> numbers) {
    string answer = "";
    vector<string> snums;
    
    for(int i = 0; i<numbers.size(); i++){
        snums.push_back(to_string(numbers[i]));
    }
    
    sort(snums.begin(), snums.end(), comp);
    
    cout << ("30" > "3") << endl;
    
    for(int i = 0; i<snums.size(); i++){
        answer += snums[i];
    }
    
    
    return answer;
}

결과는,... 33점이라는 점수를 받았다.

 

흠..

---

3. [0, 0, 0] => "0" vs "000"

이런 테스트케이스의경우, 정답은 "0"이다.

설명에 숫자로 표현할경우 너무 길어질 수 있으니까 string으로 답을 낸다고 했기때문에, 000이 되면 안된다!

=> 내림차순 정렬을 했을 때, 제일 앞에 "0"이 있으면 무조건 "0"이 정답이다.

(제일 큰 string이 "0"이면, 이것보다 작은 숫자로 된 string은 존재하지 않음 혹은 "0"만 가능함)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool comp(string a, string b){
    int numa = stoi(a);
    int numb = stoi(b);
    if(numa == 0 || numb == 0){
        return a > b;
    }
    
    // a : 30, b : 3 같은 상황
    if((numa % 10 == 0 && numa % numb == 0)){
        // a : 10, b : 5 혹은 b : 2같은 상황일 수 있음
        if((numa / numb) % 10 == 0){
            return a < b;
        }
    }
    
    // a : 3, b : 30
    if((numb % 10 == 0 && numb % numa == 0)){
        // a : 5/2, b : 10 같은 상황일 수 있음
        if((numb / numa) % 10 == 0){
            return a < b;
        }
    }
    
    return a > b;
}



string solution(vector<int> numbers) {
    string answer = "";
    vector<string> snums;
    
    for(int i = 0; i<numbers.size(); i++){
        snums.push_back(to_string(numbers[i]));
    }
    
    sort(snums.begin(), snums.end(), comp);
    
    //cout << ("30" > "3") << endl;
    
    if(!snums[0].compare("0")){
        return "0";
    }
    
    for(int i = 0; i<snums.size(); i++){
        answer += snums[i];
    }
    
    
    return answer;
}

answer를 내기 전에, 맨 앞이 "0"인지 확인하는 부분을 추가해줬다.

결과는... 똑같았다. 왜이럴까

---

4. [12, 121] => "12121" vs "12112"

정답은 12121이다 (내림차순 정렬 12 121로 해야함)

하지만 내가 위에서 작성한건,, 내림차순 정렬했을 때 121 12 순서로 된다 (사전순으로 정렬했음..)

=> compare함수를 또 바꾸자!!

 

근데,, 어떤 조건을 추가해야할지 아리송했다. 저렇게 숫자나누기로 안될것같은데....

 

그래서 방법을 찾아보니, 이 문제를 작은 부분부터 확인하면서? 푸는 사람이 보였다.

오,, 그래서 비교할 때, string a, string b를 불러오니까

=> a + b와 b + a를 비교해서 더 큰쪽으로 정렬되도록 해주면 되지 않을까? 싶었다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool comp(string a, string b){
    if(stoi(a + b) > stoi(b + a)){
        return true;
    }else{
        return false;
    }
    
    
}



string solution(vector<int> numbers) {
    string answer = "";
    vector<string> snums;
    
    for(int i = 0; i<numbers.size(); i++){
        snums.push_back(to_string(numbers[i]));
    }
    
    sort(snums.begin(), snums.end(), comp);
    
    //cout << ("30" > "3") << endl;
    
    if(!snums[0].compare("0")){
        return "0";
    }
    
    for(int i = 0; i<snums.size(); i++){
        answer += snums[i];
    }
    
    
    return answer;
}

결과는 성공!!!

 

---

이런 깔끔한 방법이 있었는데,, 쓸대없이 if문만 잔뜩 추가해서 참..ㅋㅋㅋㅋㅋ

 

사실 이런문제 만나면 모든 경우의 수를 다 찾아서 정렬하라는건가,, 싶었는데

이제 대충 어떻게 하라는건지 감이 잡힌것같다.

string으로 바꿔서 대소관계 비교해보기ㅎㅎ