프로그래머스[programmers] - 가장 큰 수 찾기(C++)[LV2]

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

입출력 예

numbers                                                                              return

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

 

문제 해석

1. numbers의 원소의 범위는 0~1000까지이다.
2. 각 numbers의 자릿수가 같다면 비교하기 편할 것이다.
   1. 하지만 numbers의 자리는 각각 다를 수 있다.
      1. 그래서 numbers의 자릿수를 일치시켜주면 비교가 편할거라고 생각했다.
      2. numbers의 자리수 후보는 1,2,3,4이다. (1~9), (10~99), (100~999), (1000)
      3. 각 자릿수의 최소공배수를 구해서 최소공배수만큼 길이를 늘려준다면 numbers의 자릿수는 같아질 것이다.
   2. 1,2,3,4의 최소공배수는 12로 나는 numbers의 원소들을 각각 12자리로 늘려주었다.
      1. 예를 들어 1을 111111111111, 23을 232323232323 이렇게 늘려주었다.
      2. 이렇게 늘려준걸 문자열 벡터에다가 넣어주고 정렬하였다.
3. 이제 큰 순서대로 answer에 넣어주면 끝이다. 자세한 설명은 구현에서 설명하겠다.

구현

1. 12개의 문자열을 이어 붙일 문자열과 (문자열, 원래 numbers의 길이)를 인자로 가지는 pair를 생성.

vector<string> a(numbers.size());
vector<pair<string, int>> p;

2. numbers의 원소들을 12개로 늘려주기.

 for (int i = 0; i < numbers.size(); i++)
{
        // a의 길이가 12가 될때까지 이어붙임.
        string str = to_string(numbers[i]);
        // cout<<str.length()<<endl;
        int size = 12 / str.length();
        // cout<<size<<endl;
        for (int j = 0; j < size; j++)
        {
            a[i] += to_string(numbers[i]);
        }
        p.push_back(make_pair(a[i], str.length()));
}

str.length()를 따로 구해주는 이유는 비교했던 문자열을 다시 원래 숫자대로 넣어줄 때 필요해서이다.

 

3. a배열과 pair P를 정렬해줌.

sort(a.begin(), a.end()); //오름차순 정렬
sort(p.begin(), p.end()); //오름차순 정렬

4. A배열의 큰 순서가 곧 numbers의 큰 순서이기 때문에 순서대로 넣어주고 원래의 문자열 길이만큼 넣어줌.

for (int i = a.size() - 1; i >= 0; i--)
{
        int size;
        size = p[i].second;
        for (int j = 0; j < size; j++)
        {
            answer += a[i][j];
        }
}

 

 

예외처리 :

테스트 케이스도 통과했는데 코드 제출을 하니까 하나의 테케에서 막혔다. 이유를 몰라서 괴로웠는데 예를 들어

[0,0,0,0]을 넣으면 0만 나와야 하는데 내 코드로는 0000이 나왔었다. 그래서 만약 numbers를 내림차순으로 정렬하고 만약 첫 번째 원소가 0이라면 뒤의 원소도 0이거나 없다는 뜻이니까 0을 리턴해줬다.

sort(numbers.begin(), numbers.end(), compare);
if (numbers[0] == 0)
{
    answer = '0';
    return answer;
}