[프로그래머스] 가장 큰수

문제 설명

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

풀이)

처음에 numbers 집합에서 원소를 순열로 선택해서 string으로 각자 바꿔 합치는 방법을 썼더니, 시간초과가 났다.

결국 방법이 생각나지 않아, 다른 분의 코드를 보고 도움을 받았다.

다른 분의 코드 풀이는 이러하다.

예를 들어 int 6과 10이 있다면,이들을 string으로 바꾼 뒤 더해본다.

"6" + "10" = "610" > "10" + "6" = "106"

6 다음에 10을 더하는 게, 값이 더 큼을 알 수 있다. 

이 성질을 이용해 정렬을 구현하면 된다.

주의점

numbers 집합의 원소가 모두 0일 경우를 고려해줘야한다.

코드)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <string> #include <algorithm> #include <vector> using namespace std; bool cmp(const string &a, const string &b){ return a + b > b + a; } string solution(vector<int> numbers) { string answer =""; vector <string> temp; for(int i=0;i<(int)numbers.size();i++){ temp.push_back(to_string(numbers[i])); } sort(temp.begin(),temp.end(),cmp); if(temp[0][0] == '0') return "0"; for(int i=0;i<(int)temp.size();i++){ answer += temp[i]; } return answer; }