[프로그래머스] 42746_가장 큰 수(c++)

 

문제 설명

 

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

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

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

 

제한 사항

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

입출력 예

numbersreturn

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

 

---

 

#C++ 첫 접근

 

-만들 수 있는 모든 경우의 수를 다 구하고 가장 큰 숫자를 결과 값으로 반환하면 된다고 생각함.

-그래서 C++에서 가장 애정하는 next_permutation을 이용하여 구현했음.

 

 

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

using namespace std;

string solution(vector<int> numbers) { //가장 큰 수 - fail
    vector<string> tmp;

    sort(numbers.begin(), numbers.end());

    do{
        string s = "";
        for(int i = 0; i < numbers.size(); i++){
            s += to_string(numbers[i]);
        }
        tmp.push_back(s);

    } while(next_permutation(numbers.begin(), numbers.end()));

    sort(tmp.begin(), tmp.end());

    return tmp[tmp.size() - 1];
} 

 

실행 결과

 

테스트 케이스는 모두 통과하나 제출한 후 시간 초과가 남.

 

제한 사항을 제대로 보지 못했다는 것을 느꼈음. C++ STL에서 제공하는 next_permutation의 경우 시간복잡도가 O(N)으로 n제한인 100,000에 do - while 안 for 문까지 고려하면 1초 안에 연산이 불가능함. 즉 터지는 코드임.

 

 

#C++ 두 번째 접근

 

-모든 경우의 수를 다 계산하면 시간복잡도에서 터지는 결과가 나오기 때문에 다른 방식으로 접근함.

-두 개의 숫자를 정렬할 때 기준을 두기로 결정함.

-두 숫자의 string 합을 비교하여 우위에 둘 숫자를 결정하게 했음.

 

 

입출력 예제 [3, 30, 34, 5, 9] 을 예로 들어보자.

 

3과 30 중에 우위를 정하는 방법은 3 + 30 => 330과 30 + 3 => 303을 비교하는 것임.

이렇게 할 경우 앞자리가 3으로 동일하더라도 어떤 것이 우위에 올지 결정할 수 있음.

 

Step 1. [3, 30, 34, 5, 9]

3 + 30 => 330, 30 + 3 => 303 ------> 330 > 303 따라서, 3이 우위가 됨.  -> 3, 30, 34, 5, 9

30 + 34  => 3034, 34 + 30 => 3430 -----> 3034 < 3430 따라서, 34가 우위가 됨. -> 3, 34, 30, 5, 9

30 + 5 => 305, 5 + 30 => 530 -----> 305 < 530 따라서, 5가 우위가 됨. -> 3, 34, 5, 30, 9

30 + 9 => 309, 9 + 30 => 930 -----> 309 < 930 따라서, 9가 우위가 됨. -> 3, 34, 5, 9, 30

 

Step 2. [3, 34, 5, 9, 30]

3 + 34 => 334, 34 + 3 => 343 -----> 334 < 343 따라서, 34가 우위가 됨. -> 34, 3, 5, 9, 30

3 + 5 => 35, 5 + 9 => 59 -----> 35 < 59 따라서, 5가 우위가 됨. -> 34, 5, 3, 9, 30

3 + 9 => 39, 9 + 3 => 93 -----> 39 < 93 따라서, 9가 우위가 됨. -> 34, 5, 9, 3, 30

3 + 30 => 330, 30 + 3 => 303 -----> 330 > 303 따라서, 3이 우위가 됨. -> 34, 5, 9, 3, 30

 

Step 3. [34, 5, 9, 3, 30]

34 + 5 => 345, 5 + 34 => 534 -----> 345 > 534 따라서, 5가 우위가 됨. -> 5, 34, 9, 3, 30

34 + 9 => 349, 9 + 34 => 934 -----> 349 < 934 따라서, 9가 우위가 됨. -> 5, 9, 34, 3, 30

34 + 3 => 343, 3 + 34 => 334 -----> 343 > 334 따라서, 34가 우위가 됨. -> 5, 9, 34, 3, 30

3 + 30 => 330, 30 + 3 => 303 -----> 330 > 303 따라서, 3이 우위가 됨. -> 34, 5, 9, 3, 30

 

 

---

 

이렇게 계속해서 구하다보면 [9, 5, 34, 3, 30]의 결과가 나옴. 

 

-cmp라는 함수를 만들어주고 위의 과정처럼 풀 수 있도록 조건을 주었음. a + b > b + a인 경우에 true가 되도록 메소드를 작성하였음. 

-sort(tmp의 처음부터, tmp의 마지막까지, cmp에 정의한 것을 기준으로) 정렬을 수행했음.

-하나 주의해야할 점은, 결과로 이어붙인 answer의 0번째 인덱스가 0인 경우 가장 큰 수가 0이라는 뜻이므로 0을 리턴해줘야 함!!

 

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

using namespace std;

bool cmp(const string &a, const string &b) { //string으로 비교 수행
	return a + b > b + a;
}

string solution(vector<int> numbers) { //가장 큰 수 - success
	string answer = "";
	vector<string> tmp;
    
	for (int i = 0; i < numbers.size(); i++) tmp.push_back(to_string(numbers[i]));
    
	sort(tmp.begin(), tmp.end(), cmp); //cmp 함수 기준으로 정렬 수행
    
	for (int i = 0; i < tmp.size(); i++) answer += tmp[i]; 
    
	if (answer[0] == '0') return "0"; //answer[0]가 0이면 가장 큰 수가 0이라는 뜻이므로 0리턴
    
	return answer;
}

 

실행 결과

 

모든 테스트 케이스가 정상적으로 실행됨.