프로그래머스 가장큰수

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

프로그래머스

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

생각

처음에 이 문제를 보고 어떻게 풀어야 할까 고민을 하다가 “string solution(vector<int> numbers)” 매개변수로 백터를 받는 다는 것을 보고 숫자를 하나씩 받아서 비교해주면서 정렬 시키면 되겠구나 생각하였다. 숫자가 한자릿 수면 그냥 정렬하면 되겠지만, 두자리나 세자릿수까지 고려해야하기 때문에 고민 좀 하였다. 예를 들어 2와 100을 비교할 때 100이 크다고 정렬하면 1002가 되버리기 때문에 2100을 간과 할 수 있게 된다. 때문에 나는 문자열로 받아서 문자열 합으로 계산하였다. 문자열로 계산하면 “2”+”100”>”100”+”2”가 성립 되기 때문에 이런식으로 정렬할 때 조건을 걸어서 접근 했다.

 

알고리즘

1. 백터에 있는 숫자들을 하나씩 문자열로 변환하여 array에 넣어준다.
2. 정렬을 해주는데 이때, compare로 조건을 걸어준다.
3. 조건은 문자열을 서로 비교해주는 건데, a + b > b + a이런식으로 조건을 달아준다.“2”+”100”>”100”+”2” 이렇게 말이다.
4. 정렬된 array배열을 전부 문자열 합으로 계산해준다.
5. 예외 처리를 해주고 최종값을 반환해준다.

 

코드

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

using namespace std;

bool compare(const string& a, const string& b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string>array;

   
    for (int number : numbers) {
       array.push_back(to_string(number));
    }
    sort(array.begin(), array.end(), compare);

    for (int i = 0; i < array.size(); i++) {
            answer += array[i];
    }

    if(answer=="000" || answer=="00")
        answer="0";

    
    return answer;
}

이렇게 하면 테스트 11번에서 실패라고 뜬다. 뭐가 문제일까…

 

 

 if(answer=="000" || answer=="00")
        answer="0";

이 부분이 문제가 있는 것 같아서 바꿔보기로 한다.

if (answer[0] == '0') // 첫 번째 숫자가 0이면 나머지도 모두 0이므로 0으로 처리
        answer = "0";

이런 식으로 첫 번째 숫자가 0이면 나머지도 모두 0으로 처리해주는 로직으로 바꿔 주었다.

 

정렬을 하고 나서 첫번째 숫자가 0이 온다는 것은 전부 0이라는 의미기 때문에 이러헥 해주었다.

if(answer=="000" || answer=="00")이거는 내가 예외 처리를 잘못 처리한 예이다.

전혀 다른 의미기 때문에 틀리게 나왔다.

 

 

수정 코드

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

using namespace std;

bool compare(const string& a, const string& b) {
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string>array;

   
    for (int number : numbers) {
       array.push_back(to_string(number));
    }
    sort(array.begin(), array.end(), compare);

    for (int i = 0; i < array.size(); i++) {
            answer += array[i];
    }

    if (answer[0] == '0')
        answer = "0";

    
    return answer;
}

그랬더니??

된다…