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

문제 링크

코딩테스트 연습 - 가장 큰 수

 

 

 

풀이

완전 탐색으로 나열해놓고 풀까 하다가 갑자기 떠올랐다...

1. 원소는 1000이하이므로 무조건 3글자 이상으로 비교되도록 글자 수를 3번 반복해서 v에 넣어준다.

(한 글자짜리가 3글자로 비교되도록)

 

2. 정렬할 때는 reverse_iterator 이용해서 사전 순 반대로 정렬했다.

(사전 순 반대로 정렬되도록)

 

3. answer에 큰 순서대로 저장되도록 더해준다.

 

주의!

0. 모두 '0'일 경우를 방지해줘야 하기 때문에 앞에 (// 예외)를 넣었다.

- max_element() 이용: 가장 큰 원소의 iterator를 리턴해주는 함수

 

// 예시

만약 {1, 123, 530, 113, 13, 403, 12} 이 있을 경우,

 

1. 을 거치면

111        -> "1"을 의미, 한 글자짜리 '1'이 있어도 "111"로 비교하기 때문에 사전대로 정렬이 가능하다.

123123123  -> "123"
530530530  -> "530"

113113113  -> "113"
131313   -> "13"
403403403  -> "403"

121212   -> "12"

 

2. 을 거치면

530530530   -> "530"
403403403   -> "403"
131313        -> "13"
123123123   -> "123"
121212        -> "12"
113113113   -> "113"
111            -> "111"

 

3. 을 거치면

answer = "53040313123121131가 된다.

 

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

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;
    if(*max_element(numbers.begin(), numbers.end()) == 0) return answer+='0';   // 예외
    for(auto e: numbers) v.push_back(to_string(e)+to_string(e)+to_string(e));
    sort(v.rbegin(), v.rend());       // 사전 순으로 정렬(반대로)
    for(auto e: v) answer+=e.substr(0, e.length()/3);
    
    return answer;
}