Even Idiots Can Make Game

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

Date/Lastmod
Section
PS
Title
Ps-Tags
Solved

#1 잘못된 접근

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#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;
}

위에서 하이라이트 된 부분에서 num의 크기의 팩토리얼 만큼의 시간이 소요되므로, 당연히 시간이 초과될 수 밖에 없다.

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

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

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

#1 문자열 병합 마법

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

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

우리는 병합되어 나온 문자열 중에서 사전 순(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은 비교 연산자로 사전순 정렬을 허용하니 단순히 저렇게 리턴하면 간단하게 사전순 정렬 비교 함수를 만들 수 있다. 2

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

#1 코드

전체 코드는 아래와 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#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" 이므로 비어있을 때의 처리를 해주어야 한다.

#1 추가 리뷰

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

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

#2 왼쪽 공백 트림

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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에 순방향의 범위를 넣어, 처음으로 찾아낸 공백이 아닌 문자를 찾아낸다.

#2 오른쪽 공백 트림

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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 콜로 순방향으로 바꿔 주어야 한다.

#1 참고 문헌

  1. 문자열 병합은 교환 법칙이 성립하지 않는다 ↩︎

  2. 만일 C 방식의 문자열 이라면 비교 연산자로 비교시 문자열을 사전순 비교하는 것이 아니라 문자열이 저장된 곳의 주소값을 비교하게 되는 것이므로 각별히 주의해야 한다. ↩︎

comments powered by Disqus