가장 큰 수

문제

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

 

리뷰

예전에 한 번 풀어봤던 문제인데, 파이썬 공부 하다가 흥미로운 풀이 법을 발견해서 C++로도 한번 구현해봤다.

간단히 요약하자면

 

1.  각 숫자를 문자열로 바꾼다.

2.  바꾼 문자열을 세번 반복해서 벡터에 저장한다.

3.  벡터를 오름차순으로 정렬한다.

 

왜 하필 세 번 반복하나?

두번만 반복해도 프로그래머스에서 기본 제공하는 테스트 케이스는 통과한다. 하지만 채점에서는 빨간불이 막뜨는데 이유는 다음과 같다.

 

예를들어 입력이 {3, 330}이라 할때, 

- 두 번 반복할 경우 만들어지는 문자열 : "33", "330~" 

- 세 번 반복할 경우 만들어지는 문자열 : "333", "330~"

("330~"에서 세번째 자리 이후는 중요하지 않으므로 생략. )

 

여기서 중요한건 "33" 과 "333"의 차이이다.

비교해보면 "33" < "330~" <  "333" 인데, 우리가 원하는 결과는 "330~" <  "333" 쪽이다. "33"은 세번째 자리가 없기 때문에 330보다 작은 문자열로 인식된다. 

 

코드

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string solution(vector<int> numbers) {

  vector<pair<string, string>> strNums;
  bool isAllZero = true;

  for (auto &num : numbers) {
    string tmp = to_string(num);
    // 세번 더하는 이유?
    // 문자열을 *세자리 이상의 수*로 만들기 위함.
    // 입력이 {3, 330}이라 하면
    // 두 번 반복할 경우 만들어지는 문자열 : "33", "330330"
    // 비교 시 "33" <  "33~" (330의 마지막 숫자인 0을 고려하지 않고 비교)
    // 세 번 반복할 경우 만들어지는 문자열 : "333", "330330330"
    // 비교 시 "333" > "330~"  (330의 마지막 숫자인 0을 고려하여 비교)

    string strForcmp = tmp + tmp + tmp;
    strNums.push_back(make_pair(strForcmp, tmp));

    // 0,0,0,0,0 인 경우 "00000"으로 출력되는 것 예방 위함
    if (num != 0)
      isAllZero = false;
  }

  //모든 숫자가 0인경우 "0"리턴
  if (isAllZero)
    return "0";

  //내림차순 정렬
  sort(strNums.begin(), strNums.end(), greater<pair<string, string>>());

  string answer = "";
  for (auto &str : strNums) {
    answer += str.second;
  }

  return answer;
}

int main(int argc, char const *argv[]) {
  vector<int> numbers = {3, 330};
  string result = solution(numbers);
  string answer = "3330";

  if (result != answer)
    cout << "오답 : " << result << " != " << answer << endl;
  return 0;
}