개요

프로그래머스: 가장 큰 수

• 문제 설명
  0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

  예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

  0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
  

접근 방식

1. 처음 떠올린 방식은 정렬의 비교함수를 직접 작성하는 방식인데 비교함수가 매우 복잡했다.
   -> 10으로 계속 나누는 방식으로 숫자 두개의 자릿수와 첫번째 숫자를 pair형으로 구한다.
   -> 자릿수가 같으면 큰 수를 앞으로
   -> 자릿수가 다르면 앞자리 비교해서 더 큰값을 앞으로
   -> 자릿수가 다른데 앞자리도 같을 때는 자릿수 더 적은 값에 10을 여러번 곱해줌으로 맞춘 후 비교했다.

2. 이 방식으로는 문제가 있는데 72, 7340이렇게 값이 들어오면
   7200, 7340을 비교하게 되어 7340이 앞으로 간다.
   하지만 7, 7340을 비교하는 상황에서 7000, 7340 이 두값을 비교하게 되면 7340이 앞으로 나가는데, 73407 < 77340이므로 답이 아니다.

3. 따라서 자릿수가 다르면서 앞글자가 같을 때는 고려할게 많다.
   고민을 하던 중, string형이 떠올랐다.
   10을 계속 나눠 자릿수와 첫 글자를 구할 필요없이
   std::to_string함수만 사용하면 string형으로 변해 알기 쉽다.

4. string형으로 변환 후, 비교하는 부분도 쉬워졌다.
   두 string형을 합치는 순서를 달리 하고 int로 변경해서 비교하면
   끝이다.

   bool comp(int a, int b) {
   
      string strA = to_string(a);
      string strB = to_string(b);
      string strAB= strA+strB;
      string strBA = strB+strA;
      
      int A=0,B=0;
      for(char elem : strAB){
          A=A*10+elem-'0';
      }
      for(char elem : strBA){
          B=B*10 + elem-'0';
      }
      if(A!=B)
          return A>B;
      else
          return false;
   }

전체 코드

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

using namespace std;

bool comp(int a, int b) {

    string strA = to_string(a);
    string strB = to_string(b);
    string strAB= strA+strB;
    string strBA = strB+strA;
    
    int A=0,B=0;
    for(char elem : strAB){
        A=A*10+elem-'0';
    }
    for(char elem : strBA){
        B=B*10 + elem-'0';
    }
    if(A!=B)
        return A>B;
    else
        return false;
}
string solution(vector<int> numbers) {
    string answer = "";
    bool isZero=true;
    sort(numbers.begin(), numbers.end(), comp);
    for (int elem : numbers) {
        if(elem!=0) isZero=false;
        answer += to_string(elem);
    }
    //다0일때 0000이따구로 뜸
    if(isZero) return "0";
    return answer;
}

문풀후생

다른 풀이를 보니 string형을 비교하는 과정에서
굳이 int로 변형하지 않고, 그대로 비교했다.

bool comp(int a, int b) {
    string strA = to_string(a);
    string strB = to_string(b);
    string strAB= strA+strB;
    string strBA = strB+strA;
    
    if(strAB!=strBA)
        return strAB>strBA;
    else
        return false;
}

이런식으로 풀 수 있다.

또한, 최종값이 0인지 비교해야한다.
예를들어 케이스가 [0, 0, 0, 0] 이런식으로 들어오면
다 이어붙이기만해서 "0000" 이렇게 답을 출력해버린다.

또한 최대케이스는 1000을 10만개 이어붙인것으로
자릿수가 4*10만이 넘는다.
이 값을 숫자로 표현하려면 long long도 오버플로우가 나므로
위 풀이처럼 모든값이 0인지 체크하거나 ,
answer값의 첫번째 원소가 0인지 봐야한다.

마지막에 string형을 숫자로 고쳐서

long long isZero=0;
for(char elem : answer){
	isZero=isZero*10 + elem-'0';
}
if(isZero==0) return "0";
return answer;

이런식으로 0인지 체크하려하면 isZero가 터져서 답이 안나온다.