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

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

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

 

1. 서론

 

진짜 개짜증 나는 문제^^;; 아니? 문제가 아니라 내가 짜증 나는 사람일지도 ㅎㅎ

진짜 어렵게 생각하면 끝이 없는데 생각보다 컴퓨터가 자동으로 처리할 수 있는 일이 많다는 것을 일깨워 준 문제이다,,

 

2. 문제 풀이

 

주어진 숫자들을 통채로 붙였을 때 가장 큰 조합을 찾아서 구하는 문제이다.

 

나는 그래서 처음에는 정렬로 할까 하다가 정렬 조건이 까다로울 것 같아서 순열로 최댓값을 구하려 했다. 그런데 바로 시간 초과 크리 먹고 다시 정렬로 돌아왔다. 정렬하는 조건이 숫자의 값과, 길이 둘 다 상관이 없고 더했을 때 같은 큰 값을 구해야 한다. 그래서 처음에는 첫 번째 값이 같은 경우에는 숫자의 맨 뒤에서부터 비교해서 그 값이 큰 경우가 앞에 오도록 하고 나머지 경우에는 그냥 역순 정렬로 앞의 값이 큰 게 앞으로 오게 했다. 나름 괜찮은 방법이라고 생각했고 온갖 반례를 통과했지만 이상하게 돌리면 1~6번과 11번이 틀리는 것이다... 글로는 짧게 줄였지만 여기까지 오는데도 꽤 오랜 시간이 걸렸다. 그리고 나는 이 이상의 방법을 떠올릴 수 없다는 것을 깨닫고 검색을 갈겼다.

 

https://mungto.tistory.com/22

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

 

그리고 이 글을 보고 나는 기절할 뻔 했다. 난 도대체 얼마나 시간을 낭비한 거지...? 이게 되는 거라고...?

내가 놓친 점은 두 가지였다.

 

1. 문자열의 크기를 그냥 비교할 수 있다는 것

2. 0인 경우의 처리

 

1번 같은 경우는 물론 모르는 것은 아니다. 근데 떠올리지 못한 것도 있지만 그냥 a + b 이러면 뭔가 그 길이? 크기? 만 비교될 것 같다는 편견에 사로잡혀 있었나...? 따지고 보면 각자 아스키코드가 있으니까 저렇게 대충 해도 그 크기가 정확하게 비교가 될 텐데 왜 몰랐지, 못 떠올렸지... 눈물(ㅠ.ㅠ)

 

2번의 경우 정렬이 이미 문자열인 상태에서 진행되기 때문에 "00" 이런 식으로 답이 나올 수 있기 때문에 그냥 "0"으로 출력되게 처리해줘야 한다. (11번 테케가 이것이다)

 

3. 코드 설명

 

#include <string>
#include <vector>
#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> s;
    
    for (int i = 0; i < numbers.size(); i++)
        s.push_back(to_string(numbers[i]));
    
    sort(s.begin(), s.end(), compare);
    
    for (int i = 0; i < s.size(); i++)
        answer += s[i];
       
    if (answer[0] == '0')
        answer = "0";
    
    return answer;
}

 

숫자들을 문자열로 변환하고 정렬해준다. a + b > b + a => 둘 중 더 큰 것 반환...

0 처리하기...

 

허무해... 시간 아까워.... 이 문제 여러분은 풀지 마요.... 다른 문제 풀기를.