LV2.가장 큰 수

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

프로그래머스

---

문제 내용 :

0 또는 양의 정수가 담긴 배열 하나를 인자값으로 줌

배열 원소를 각 이어 붙였을때 가장 큰 수를 반환하는 문제

 

문제 풀이 :

[숫자들의 조합 경우의 수를 찾음 -> 제일 큰값을 반환]

시간 복잡도로 인하여 바로 오답처리 

 

가장 큰 수를 뽑기 위한 조건 

1.배열의 원소(숫자)값의 제일 첫번째 자리가 커야된다.

-> ex) 6 , 10 -> 첫번째 자리 대소비교 ( 6 > 1 ) , 6이 앞으로

2.첫번째 자리가 똑같은 경우 , 해당 숫자를 앞뒤로 붙였을때 큰값을 앞에 붙여야한다 

-> ex) 3 , 34 -> 첫번째 자리가 똑같음 -> 앞뒤로 숫자를 붙여 대소비교 (334 < 343) , 343이 앞으로

 

이 2조건을 사용하여 숫자를 정렬한뒤 문자를 붙이면 원하는 결과값이 나온다.

 

[코드영역]

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

//알고리즘 헤더에 sort 함수에 비교자 변경해서 풀었음
//비교자에서 해당 수자를 문자열로 바꾸고 문자열 제일 앞 숫자가 같으면
//해당 숫자문자열을 합친뒤 크기를 비교하여 true인경우 정렬을 하는식으로

//비교자의 해당 숫자의 문자열 앞이 다른경우 대소비교하여 true인경우 정렬 

using namespace std;

bool compare(int a, int b)
{
     string str_lhs = to_string(a) ;
     string str_rhs = to_string(b) ;
    
    switch(str_lhs.front() == str_rhs.front() )
    {
        case true:
            if(str_lhs+str_rhs > str_rhs + str_lhs) { return true;}
            break;
        case false:
            if(to_string(a).front() > to_string(b).front())  {return true;} 
            break;
    }
  
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";
        
    sort(numbers.begin(),numbers.end(),compare);
   
    //정렬된 배열 제알 앞이 0인경우 숫자 완성이 안됬기에 0문자열 리턴 
    if(numbers.front() == 0 ) { return "0";}
    
    for(int num : numbers) {  answer += to_string(num);}

    return answer;
}