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

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

코딩테스트 고득점 Kit > 정렬

가장 큰 수 | 문제 바로가기

문제풀이 (2022-01-21 FRI 💻)

🤔 사담 + 🚨 간과 또는 실수한 부분

처음에는 쉽게 순열을 활용해서 풀면 되겠꾼! 했는데 시간초과가 나버렸다..
순열은 사실 상 가능한 모든 경우의 수를 다 만들어서 확인하는 것이기 때문에
굉장히 비효율적..이라고 할 수 있다 💧

그래도 오랜만에 순열 로직 복습해서 유의미한 시간이었다 (?)
뭔가 아까워서 아래 코드에 주석처리 해두었다
⭕ 물론 C++ algorithm 헤더에 포함된 next_permutation으로 순열을 구할 수도 있다

⭐ 풀이의 핵심

시간 초과를 해결할 방법을 찾지 못하여
구글링을 통해 다른 분들의 코드를 좀 참고하여 수정을 진행했다

👉 사용자 정의 cmp 함수를 만들어서 sort에 정렬 기준으로 넣어주는 방식을 찾았다
cmp 함수의 경우 string 두 개를 비교하는데
두 string을 이어붙이는 두 가지 방법 중 더 큰 것을 반환하도록 하면 된다
ex) string "7"과 string "31"을 이어붙이는 경우,
"7"+"31" = "731"</span> 이 "31" + "7" = "317" 보다 크므로 "731"이 반환된다

👉 한 가지 유의할 점은 string 형의 숫자를 비교하는 작업이기 때문에
numbers 원소 중 0이 가장 큰 숫자 (+numbers의 길이가 2 이상) 일 때

• numbers의 길이는 1 이상 100,000 이하입니다.
• numers의 원소는 0 이상 1,000 이하입니다.

라는 조건에 따라 answer는 '00', '000'과 같은 요상한 (?) 값이 될 수 있기 때문에
answer = '0' 으로 answer 값을 적절히 바꿔줘야 한다
ex) vector<int> numbers = { 0, 0, 0 } 일 경우 answer가 "000"이 될 수 있음

🔽 코드 (C++)

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

using namespace std;

bool cmp(const string &x, const string &y) {
    return x+y > y+x;
}

string solution(vector<int> numbers) {
    string answer = "";
    int N = numbers.size();
    
    // string으로 변환
    vector<string> strings;
    for (int i=0; i<N; i++) {
        strings.push_back(to_string(numbers[i]));
    }

    // 정렬 (cmp 함수 : 숫자 두 개씩 이어붙인 값 비교)
    sort(strings.begin(), strings.end(), cmp);

    // 정렬한 순서대로 숫자 이어붙여서 answer 값 구하기
    for (int i=0; i<N; i++) {
        answer += strings[i];
    }

    // 주어진 numbers에서 가장 큰 값이 0인 경우 answer = '0' 처리
    if (answer[0] == '0') {
        answer = '0';
    }

    return answer;
}

/* cf) permutation 활용 시 시간 초과
vector<string> candidates;

void permutation(vector<string> strings, int depth, int n) {
    if (depth == n) {
        string s = "";
        for (int i=0; i<n; i++) {
            s += strings[i];
        }
        candidates.push_back(s);
    }

    else {
        for (int i=depth; i<n; i++) {
            swap(strings[depth], strings[i]);
            permutation(strings, depth+1, n);
            swap(strings[depth], strings[i]);
        }
    }
}

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

    vector<string> strings;
    int N = numbers.size();
    for (int i=0; i<N; i++) {
        strings.push_back(to_string(numbers[i]));
    }
    permutation(strings, 0, N);
    sort(candidates.begin(), candidates.end(), greater<>());
    answer = candidates[0];

    return answer;
}
********************************/