가장 큰 수 - 프로그래머스, c++

 

- 문제 풀이

"정렬"을 사용하는 문제였다.

문제 풀이 전 #include <algorithm> 의 sort 함수에 대해 알아보겠다.

1. 배열 sort (오름차순)

     sort( arr, arr+N ); 

2. vector sort (오름차순)

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

3. vector sort (내림차순)

     sort( temp.begin(), temp.end(), greater<int>() );

4. vector sort시 compare 함수를 만들어서 그에 따라 정렬, 따로 bool형의 compare함수를 정의해야 함

     sort( temp.begin(), temp.end(), compare );

5. 연산자 오버로딩을 통한 sort

 

 

- 코드

처음에 작성한 코드는 다음과 같다.

하지만 복잡도 문제로 실패하였다.

코드를 더 간단하게 만들어야 했다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

    sort(numbers.begin(), numbers.end());
    
    int count = 0;
    int n = 9;
    string strtemp;
    
    while( count<numbers.size()-1 ) {
        for(int i=numbers.size()-1; i>=0; i--) {
            strtemp = to_string(numbers[i]);
            if( n==strtemp[0] ) {
                answer += strtemp;
                count++;
            }
        }
        n--;
    }
    
    return answer;
}

 

 

최종으로 제출한 코드는 다음과 같다.

이 문제는 여러 정렬 방법 중 compare함수를 이용한 정렬이 필요한 문제였다.

1. 코드에 필요한 문자열과 벡터를 선언한다.

2. for문을 통해 vector "numbers"에 있는 값을 vector "temp"에 옮겨 저장한다.

vector "numbers"는 int형이기 때문에 활용할 때 편리하게 하기 위해 string형의 vector "temp"를 사용했다.

int형을 string형으로 변환하기 위해 to_strint()함수 사용했다.

3. sort() 함수를 통해 vector "temp"의 값을 큰 순서대로 정렬하였다.

정렬할 땐 cmp함수를 사용해 두 문자를 합쳤을 때 더 큰 수를 만드는 방향으로 정렬되도록 했다.

4. 만약 최종으로 정렬한 "temp"가 000...과 같은 형식일 땐 그냥 0만 가지도록 예외경우도 처리해주었다.

5.마지막으로 최종적으로 정렬한 (string형의) 숫자들을 하나씩 문자열 "answer"에 넣어준다.

#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[0] == "0")        
        return "0";
    
    for (auto num : temp)
        answer += num;
    
    return answer;
}