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

문제

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

프로그래머스

• 소요 시간 : 35분
• 난이도 : LV 2

접근 방법

1. 순열

순열을 이용하여 모든 경우의 수를 비교해본 후 가장 큰 문자열을 반환하였다.

 

2. 정렬

2개의 문자열을 붙였을 때 큰 문자열이 되도록 정렬 함수를 구현하였다.

ex. 30, 3

30+3 = 303 vs 3+30 = 30

=> 3, 30 으로 정렬 

 

나의 풀이

1. 순열

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    
     
    sort(numbers.begin(), numbers.end());
    
    
    do {
        string str;
        for(int i : numbers) {
            str += to_string(i);
        }
        
        if (answer < str) {
            answer = str;
        }
        
    } while(next_permutation(numbers.begin(), numbers.end())); 
    
    
    return answer;
}

 

결과 : 시간 초과 

 

numbers의 길이가 10만까지인데,  순열의 시간복잡도는 O(n!) 이므로 당연히 시간 초과가 났다.

 

2. 정렬

1차

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

using namespace std;

bool compare(string a, string b) {
    string ab = a + b;
    string ba = b + a;
    return ab > ba;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    // string 으로 변환
    vector<string> stringNumbers;
    
    for(int num : numbers) {
        string stringNum = to_string(num);
        stringNumbers.push_back(stringNum);
    }
        
    sort(stringNumbers.begin(), stringNumbers.end(), compare);
    
    for(string strNum : stringNumbers) {
        answer += strNum;
    }
    
    return answer;
}

 

결과 : 11번 테스트 케이스 실패 

 

모든 문자가 0일 경우를 고려해주어야 한다. 

반례)
입력값 => [0, 0, 0]
기댓값 => "0"
출력값 => "000"

 

https://school.programmers.co.kr/questions/75367

프로그래머스

 

2차

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

using namespace std;

bool compare(string a, string b) {
    string ab = a + b;
    string ba = b + a;
    return ab > ba;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    // string 으로 변환
    vector<string> stringNumbers;
    
    for(int num : numbers) {
        string stringNum = to_string(num);
        stringNumbers.push_back(stringNum);
    }
        
    sort(stringNumbers.begin(), stringNumbers.end(), compare);
    
    for(string strNum : stringNumbers) {
        answer += strNum;
    }
    

    // 모두 0인 경우 : 맨 앞자리 0일 것
    if (answer[0] == '0')
        answer = "0";
    
    return answer;
}

 

 

결과 : 정답

 

정리

언제나 코드 짜기 전에 내 알고리즘의 시간복잡도를 고려하자.