프로그래머스 42746 LV2 가장 큰 수

잘못된 접근

모든 순열을 다 검사하려고 하였는데, 순열이 팩토리얼임을 항상 명심해야 했었다. $n$이 조금만 커져도 순열은 시간이 기하 급수적으로 올라간다.

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

using namespace std;

string make_string(vector<int> const &v) {
  string  s = "";

  for (auto it = v.begin(); it != v.end(); ++it) {
    s += to_string(*it);
  }
  
  return s;
}

string solution(vector<int> nums) {
  sort(nums.begin(), nums.end());
  
  string max_s = "";
  
  do {
    max_s = max(make_string(nums), max_s);
  } while (next_permutation(nums.begin(), nums.end()));
    
  return max_s;
}

위의 do ... while (next_permutation(...)) 반복문에서 num의 크기의 팩토리얼 만큼의 시간이 소요되므로, 당연히 시간이 초과될 수 밖에 없다.

다음처럼 생각했으면 이런 접근을 진작에 하지 않았을 것이다.

최댓값을 구하는 것이므로 완전 탐색을 이용한다면 nums 배열의 크기의 팩토리얼 만큼 순회해야 한다. 복잡도는 $O(n!)$ 이고 심지어 num의 범위도 $[1, 100000]$이므로 이는 잘못된 접근이다.

그렇다면 최대 값을 구하는 공식이 있지 않을까?

문자열 병합 마법

최종 생성된 문자열이 사전순으로 크기만 하면 된다.

어떤 문자열 l와 r를 병합하는 방법은 두 가지인데, lr처럼 병합하거나, rl 처럼 병합한다. ¹

우리는 병합되어 나온 문자열 중에서 사전 순(Lexicographically)으로 앞선 문자열을 원하는 것일 뿐이다.

std::sort에 넘길 비교 함수를 다음과 같이 작성한다고 생각해 보자.

auto cmp = [] (auto l, auto r) {
  auto lr = to_string(l) + to_string(r);
  auto rl = to_string(r) + to_string(l);

  return lr > rl;
};

std::string은 비교 연산자로 사전순 정렬을 허용하니 단순히 저렇게 리턴하면 간단하게 사전순 정렬 비교 함수를 만들 수 있다. ²

각 숫자끼리 “이어 붙여서 더 큰 걸” 계속해서 앞으로 보내면, 결국 전체 문자열도 사전순으로 가장 큰 것이 된다.

코드

전체 코드는 아래와 같다.

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

#include <iostream>

using namespace std;

string make_string(vector<int> const &nums) {
    string str = "";
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        str += to_string(*it);
    }
    return str;
}

string solution(vector<int> nums) {
    auto cmp = [](auto l, auto r) {
        auto lr = to_string(l) + to_string(r);
        auto rl = to_string(r) + to_string(l);

        return lr > rl;
    };

    sort(nums.begin(), nums.end(), cmp);
    
    auto answer = make_string(nums);

    // 0 l-trim
    auto it = find_if(
        answer.begin(), answer.end(), 
        [](auto c) {return c != '0';}
    );
    answer.erase(answer.begin(), it);

    if (answer.empty()) 
        answer = "0";
    
    return answer;
}

여기서 한 가지 더 처리를 해 주어야 하는데, 최종적으로 숫자인 문자열을 반환해야 하므로, 맨 앞 자리수에 연속된 '0'들을 제거해 주어야 한다. 왼쪽에서 0으로 한번 트림(Trim)해 주어야 하며, 마지막으로 처음에 전달받은 배열의 모든 원소가 0이었던 경우, 모든 것이 트림되지만, 이 때의 수는 "0" 이므로 비어있을 때의 처리를 해주어야 한다.

추가 리뷰

보통 문자열 트림은 왼쪽과 오른쪽에 대해서 공백을 제거하는 형태로 많이 쓰인다.

이 문제를 해결하는 김에, 해당 함수들도 복습할 겸 구현하였다.

왼쪽 공백 트림

string l_trim(string const &s) {
  auto sc(s);

  auto it = find_if(
    sc.begin(), sc.end(), 
    [](auto c){ return !isspace(c); }
  );

  sc.erase(sc.begin(), it);
  return sc;
}

find_if에 순방향의 범위를 넣어, 처음으로 찾아낸 공백이 아닌 문자를 찾아낸다.

오른쪽 공백 트림

string r_trim(string const &s) {
    auto sc(s);

    auto it = find_if(
      sc.rbegin(), sc.rend(), 
      [](auto c){ return !isspace(c); }
    ).base();
    
    sc.erase(it, sc.end());
    return sc;
}

find_if에 역방향의 범위를 넣어, 처음으로 찾아낸 공백이 아닌 문자를 찾아낸다.

뒤에서부터 세어나가 찾아낸다고 보면 된다.

유의할 점은 find_if의 반환이 이번에는 역방향 반복자이기 때문에 .base 콜로 순방향으로 바꿔 주어야 한다.

참고 문헌

• How to trim a std::string/StackOverflow