코딩문제/프로그래머스
2레벨 : 가장 큰 수
Drill_Labito
2020. 7. 18. 18:22

현재 내 실력으론 해결법이 떠오르지 않아 인터넷의 솔루션을 참고하였다.
정수를 문자형으로 바꿔서, 처리해야지 까지는 생각하였지만, 모든케이스, 즉 각 숫자 더한 값에 따라 비교를 하나씩 전부다 함으로써, 시간복잡도가 n! 로 나와 시간초과 문제에서 막혀있었다.
이를 효율적으로 하기 위해, 다른사람의 풀이를 본 결과, string vector를 하나 더 만들어서 기존 입력의 vector 인자들을 정렬 한 다음, (정렬시, 각 더한 결과가 더 큰쪽으로 오름차순 정렬되게) 이를 조건에 따라 먼저 나온 문자가 0이면 answer 에 0을 그 외의 경우, 해당 인자를 answer 값에 더해줌으로 원하는 정답을 리턴하는 경우로 해결을 하였다.
아직 실력이 많이 부족함을 깨닫고 좀더 많은 문제를 풀어보고 사고력을 키워야 함을 느꼈다.
소스 코드는 아래와 같다.
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(string a, string b){
return a+b>b+a;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> string_numbers;
for(auto number:numbers){
string_numbers.push_back(to_string(number));
}
sort(string_numbers.begin(), string_numbers.end(), compare);
if(string_numbers[0] == "0"){
return "0";
}
for(auto string_number : string_numbers)
answer += string_number;
return answer;
}