99클럽 코테스터디 11일차 TIL 가장 큰 수

프로그래머스 가장 큰 수

문제 링크

문제 설명

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

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

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

제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

6, 10, 2 가 입력으로 들어오면 6210 이런식으로 가장 큰 수가 나올 수 있게 구현하는 문제

 

문제 풀이

algorithm 헤더에 내장되어있는 sort 함수를 활용하여 풀이했다.

최대로 주어지는 숫자의 크기는 100,000 이고, 갯수는 1,000개 정도이기 때문에 내장함수 sort를 써도 무방하다고 판단했다

 

sort 에 들어가는 compare 함수를 custom 해줬다.
두 숫자를 비교할 때, string 형태로 변형해서 가장 앞의 수가 크면 가장 앞으로 가게했다.
맨 앞 두 숫자가 같을 경우, 그냥 내림차순으로 정렬하면 문제가 발생할 수 있다.

• 만약 3과 30과 34가 각각 리스트에 존재한다 할때, 이 숫자로 만들 수 있는 가장 큰 수는 34330 인데, 그냥 내림차순으로 정렬하고 붙이면 34303 이 된다.
• 정렬 조건에서 string 으로 변환한 두 숫자를 임시로 붙여보고 더 큰쪽이 앞으로 갈 수 있게 해줬다. 
• string tmpA = to_string(a), tmpB = to_string(b); if (tmpA+tmpB > tmpB+tmpA) return true;

정렬했을 때, 기본적으로 내림차순 정렬이기 때문에, 가장 앞에 있는 숫자가 0 이면 리스트에 존재하는 모든 숫자가 0 이라는 뜻이기 때문에 "0"을 리턴해줬다.

 

코드

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

using namespace std;

bool compare(int a, int b) {
    string tmpA = to_string(a), tmpB = to_string(b);
    if (tmpA+tmpB > tmpB+tmpA) return true;
    return false;
}

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

    // 내림차순으로 정렬, 맨 앞자리가 가장 큰수
    sort(numbers.begin(), numbers.end(), compare);

    if (numbers[0] == 0) return "0";

    for (auto it=numbers.begin(); it!=numbers.end(); it++) {
        // cout << *it << " ";
        answer += to_string(*it);
    }

    return answer;
}

 

회고

compare 을 이렇게까지 조작해 보는 건 처음이었는데 의외로 생각했던데로 잘 되서 신기했다. 이게 내장함수의 힘인가

 

전체 수가 0인 경우는 생각하지 못했어서 좀 해멨는데, 문제에 0 또는 양의 정수라고 써있던걸 뒤늦게 확인했다. 문제를 꼼꼼히 읽는다고 읽는데 아직도 잘 안되는 것 같다.