가장 큰 수 C++ (정렬)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

 

---

1. 문제 설명

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"
[0, 0, 0, 0, 0, 0, 0]	"0"

 

---

2. 문제풀이

문제를 풀때 2가지 방법이 생각났었습니다. 1. 제일 앞자리를 비교한다. , 앞자리가 같다면 길이가 짧은걸로, 길이가 같다면 그뒤에자리가 큰순으로 정렬한다. 2. string으로 변환한다. 합쳐서 큰값으로 정렬한다. 그래서 저는 string으로 변환해서 푸는 방법으로 했습니다.   string을 그냥 비교하게되면 원하는대로 정렬이 되지 않습니다. 기본은 오름차순인데다가 내림차순으로 바꿔도 3, 30이 있다고하면 330이 나와야 하는데 303이 나와버립니다. 그래서 비교함수를 커스텀해야합니다.   방법은 두개를 더했을때 큰수가 앞에나오도록 해야합니다. 예를 들어서 6하고 10이 있다고 합시다. 6+10인 610과 10+6인 106이 있습니다. 더한 값을 비교합니다. (모르겠다면 소스코드를 확인해주세요)   커스텀한 함수를 이용하여 정렬이 끝났다면 예외처리를 해줍니다. 만약 0만 여러개라면 0하나만 리턴해야합니다.   예외처리가 끝났다면 앞에서부터 string을 더해서 반환합니다.

---

3. 소스코드

 

3.1 주석없는 코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
bool cmp(string a, string b) {
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;
    for (auto num : numbers)
        temp.push_back(to_string(num));
    sort(temp.begin(), temp.end(), cmp);
    if (temp.at(0) == "0")        return "0";
    for (auto num : temp)
        answer += num;
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//합친 문자 비교해서 큰순으로 정렬하기, ex ) 6, 10 이 있다면 610과 106하고 어떤게 큰지 비교
// 610이 더크므로 6, 10순으로 정렬하게 된다.
bool cmp(string a, string b) {
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;
    //string으로 바꾼후 벡터에 집어넣는다.
    for (auto num : numbers)
        temp.push_back(to_string(num));
    //더할때 오름차순으로 정렬한다.
    sort(temp.begin(), temp.end(), cmp);
    //처음 숫자가 0이라면 0을 반환
    if (temp.at(0) == "0")        return "0";
    //처음부터 끝까지 문자열 합치고 리턴
    for (auto num : temp)
        answer += num;
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
//합친 문자 비교해서 큰순으로 정렬하기, ex ) 6, 10 이 있다면 610과 106하고 어떤게 큰지 비교
// 610이 더크므로 6, 10순으로 정렬하게 된다.
bool cmp(string a, string b) {
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;
    //string으로 바꾼후 벡터에 집어넣는다.
    for (auto num : numbers)
        temp.push_back(to_string(num));
    //더할때 오름차순으로 정렬한다.
    sort(temp.begin(), temp.end(), cmp);
    //처음 숫자가 0이라면 0을 반환
    if (temp.at(0) == "0")        return "0";
    //처음부터 끝까지 문자열 합치고 리턴
    for (auto num : temp)
        answer += num;
    return answer;
}
 
void print(vector<int> numbers, string answer) {
    string t = solution(numbers);
    if (t == answer)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main(){
    print({6, 10, 2}, "6210");
    print({ 3, 30, 34, 5, 9 }, "9534330");
    print({0,0,0,0,0,0,0}, "0");
    return 0;
}

4. 결과