👱‍♀️ ansohxxn

👱‍♀️ ansohxxn

개인적인 필기 노트

[고득점Kit][정렬] 가장 큰 수 ⭐⭐

Date:     Updated:

카테고리:

태그:

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[정렬] 가장 큰 수

난이도 ⭐⭐

문제

image

배울게 많은 문제였다!


내 풀이 (feat. 삽질 과정) ❌

정답인 풀이는 아래에 있습니다. 1 ~ 3 차 이 풀이들은 제 틀린 풀이라는 것에 유념해주세요!

  • 모 ~ 든 조합을 다 따져본 후 최대값을 구하는건 엄청나게 비효율적이라는 것은 인지 하고 시작했다.
    • numbers의 길이가 100,000 까지도 갈 수 있기 때문에
  • ‘📢틀린’ 내 풀이의 아이디어
    • 붙여 이었을 때 큰 수를 만들 수 있는 것을 기준으로 numbers을 내림 차순 정렬을 한 후 차례대로 원소들을 이어 붙이면 그것이 바로 정답!
      • sort 함수에 넘길 비교 함수를 따로 마련한다.
      • 정렬 기준 👉
        • 왼쪽 자릿수부터 검사하여 비교한 자릿수가 더 큰 것이 더 크다고 정의 내린다. 단, 두 자릿수가 같다면 그 뒤에 있는 자릿수끼리 비교한다.
        • 예를 들어 112 와 12 을 비교한다면 12112 > 11212 로 12 가 112 보다 앞서서 붙여주는게 더 크다.
          • 우선 비교하기에 앞서 자릿수들을 구분한다. 112 는 1, 1, 2 로 12 는 1, 2 로.
            • 나는 이 자릿수들을 2 개의 스택에 각각 저장하기로 했다.
            • 자릿수 계산은 10을 나눈 나머지로 계산되므로 오른쪽 끝 자릿수부터 저장된다.
          • 스택에 저장되므로 가장 먼저 빠져나오는 것은 왼쪽 끝자릿수이다.
            • 1 과 1 을 비교 👉 같으므로 두 스택을 pop 한다.
            • 1 과 2 을 비교 👉 1 < 2 이므로 112 < 12 라고 판단한다.
          • 만약 스택의 사이즈가 둘 다 1 인데 또 값이 같다면 두 수가 완전 같은 수라고 판단한다.
          • 스택의 사이즈가 1 은 아니지만 두 수가 같다면 스택에서 pop 한다.
    • 이렇게 나는 위와 같이 두 수를 비교할 수 있으며 이와 같은 기준으로 정렬하면 될 것이라고 생각했다.


1 차 풀이

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

using namespace std;

bool compare (const int & a, const int & b)
{ 
    stack<int> stack_A;
    stack<int> stack_B;
    int quo_a = a, quo_b = b;
    
    while(quo_a > 0)
    {
        stack_A.push(quo_a % 10);
        quo_a /= 10;
    }
    
    while(quo_b > 0)
    {
        stack_B.push(quo_b % 10);
        quo_b /= 10;
    }
    
    while(true)
    {
        if(stack_A.top() == stack_B.top())
        {
            if (stack_A.size() == 1 && stack_B.size() == 1)
                return stack_A.top() == stack_B.top();
            if (stack_A.size() > 1)
                stack_A.pop();
            if (stack_B.size() > 1)
                stack_B.pop();
        }
        else
            return stack_A.top() > stack_B.top();
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    for(auto & elem : numbers)
    {
        answer += to_string(elem);
    }
    
    return answer;
}

결론적으로 이 풀이는 런타임 에러가 나는 테스트 케이스가 존재할 수 있다.

  • 런타임 에러가 나는 케이스 👉 원소가 0 일 때
    • 원소가 0 이면 while(quo_a > 0) 혹은 while(quo_b > 0) 에 걸리지 않아 while 문을 돌지 않기 때문에 스택에 아무것도 추가하지 못한 채 빈 스택으로 남게된다.
    • 그런 상태에서 stack_A.top(), stack_B.top()빈 스택에 접근하려고 하니 런타임 에러가 발생하는 것
  • 🎵 교훈
    • 런타임 에러 segmentation fault (core dumped)에러가 발생한다면 빈 컨테이너 혹은 아무것도 없는 null 상태에서 그 빈 인스턴스의 함수를 호출하려고 하진 않는지 그런 경우는 혹시 없는지 검사를 꼭 해야 한다.
      • 런타임 에러가 발생하므로 stack.top() 호출 하기 전에 빈 스택이 되는 경우는 없었는지 체크했어야 했다.
  • 아래와 같이 고쳐주었다. 
      while(true)
  {
      stack_A.push(quo_a % 10);
      quo_a /= 10;
      if (quo_a == 0) break;
  }
    
  while(true)
  {
      stack_B.push(quo_b % 10);
      quo_b /= 10;
      if (quo_b == 0) break;
  }


2 차 풀이

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

using namespace std;

bool compare (const int & a, const int & b)
{ 
    stack<int> stack_A;
    stack<int> stack_B;
    int quo_a = a, quo_b = b;
    
    while(true)
    {
        stack_A.push(quo_a % 10);
        quo_a /= 10;
        if (quo_a == 0) break;
    }
    
    while(true)
    {
        stack_B.push(quo_b % 10);
        quo_b /= 10;
        if (quo_b == 0) break;
    }
    
    while(true)
    {
        if(stack_A.top() == stack_B.top())
        {
            if (stack_A.size() == 1 && stack_B.size() == 1)
                return stack_A.top() == stack_B.top();
            if (stack_A.size() > 1)
                stack_A.pop();
            if (stack_B.size() > 1)
                stack_B.pop();
        }
        else
            return stack_A.top() > stack_B.top();
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    for(auto & elem : numbers)
    {
        answer += to_string(elem);
    }
    
    return answer;
}

결론적으로 이 풀이는 시간 초과, 런타임 에러 가 되는 테스트 케이스가 존재할 수 있다.

  • 처음에는 이해하지 못했다. 아무리 봐도 1 억번 연산을 넘기지는 않는데 도대체 왜 시간 초과가 될까..!
  • 📢 문제는 return stack_A.top() == stack_B.top();에 있었다. a < b 를 만족하는 관계 뿐만아니라 a == b 두 값이 같은 경우에도 true를 리턴 하는 경우가 문제였던 것이다.
    • 이러한 코드는 strict weak ordering을 위반하기 때문에 정렬이 정상적으로 이루어지지 않는다.
    • 정렬을 하기 위해 두 수의 크기 비교를 할 때 항상 **strict weak ordering** 조건들을 반드시 만족해야 한다.
      • 1️⃣ x < y 가 참이면 y < x 는 false 여야 한다.
      • 2️⃣ x < y 이고 y < z 이면 x < z 도 참이어야 한다.
      • 3️⃣ a <= b 이고 b <= a 이고 b <= c 이고 c <= b 라면 a = b = c 이다. 따라서 a <= c 이고 c <= a 인 ` a = c`도 성립해야 한다.
      • 4️⃣ 연산자 < 에 대해서 a < a 는 false 라는 것을 항상 보장해야 한다.
      • 위 조건들이 만족되지 않으면 여러 원소들을 정렬하는데 혼돈의 카오스를 빚을 것이다! 명확하게, 안정적으로 정렬되지 못한다.
    • 위의 조건들에 의해 같은 것 끼리의 < 비교 연산은 반드시 false를 리턴해야 한다.
      • 난 같은 경우에도 true를 리턴하게끔 했기 때문에 STL 비교함수가 혼란을 겪은 것이다.
      • STL 비교 함수는 “동등한가?”가 아닌 “첫번 째 것이 두번째 것 보다 작은가?”라고 묻는 다는 것을 기억하자.
        • It sorts only different numbers. You should always use < or > to compare things. You should have no reason to use <= or >= operator.
  • 🎵 교훈
    • 비교함수를 구현할 땐 <=, >= 일 때 true 로 리턴하게끔 하면 안되고 반드시 >, < 한가지 경우에만 true를 리턴하게끔 명확히 해야 한다.
  • 아래와 같이 바꿔 주었더니 시간 초과, 런타임 에러는 사라졌다. 
    if (stack_A.size() == 1 && stack_B.size() == 1)
      return false;  // 같은 경우 true가 아닌 false를 리턴하게끔 바꿨다.


3차 풀이

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

using namespace std;

bool compare (const int & a, const int & b)
{ 
    stack<int> stack_A;
    stack<int> stack_B;
    int quo_a = a, quo_b = b;
    
    while(true)
    {
        stack_A.push(quo_a % 10);
        quo_a /= 10;
        if (quo_a == 0) break;
    }
    
    while(true)
    {
        stack_B.push(quo_b % 10);
        quo_b /= 10;
        if (quo_b == 0) break;
    }
    
    while(true)
    {
        if(stack_A.top() == stack_B.top())
        {
            if (stack_A.size() == 1 && stack_B.size() == 1)
                return false;
            if (stack_A.size() > 1)
                stack_A.pop();
            if (stack_B.size() > 1)
                stack_B.pop();
        }
        else
            return stack_A.top() > stack_B.top();
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    for(auto & elem : numbers)
    {
        answer += to_string(elem);
    }
    
    return answer;
}

이 풀이는 틀렸습니다

  • 왜 틀렸냐면 0, 0, 0, 0 모두 0 인 케이스를 고려하지 않았기 때문이다.
    • 이런 경우엔 "0000"가 되는 것이 아닌 "0"이 되어야 한다.
    • 이런 경우를 커버하기 위해 solution 함수에 아래와 같은 코드를 추가해주었다. 
          if (numbers[0] == 0)  // 내림차순 정렬이니 첫번째 원소가 0 이면 그냥 그 numbers 배열의 원소는 전부 0 이라는 뜻 
        return "0";


이 풀이의 한계점

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

using namespace std;

bool compare (const int & a, const int & b)
{ 
    stack<int> stack_A;
    stack<int> stack_B;
    int quo_a = a, quo_b = b;
    
    while(true)
    {
        stack_A.push(quo_a % 10);
        quo_a /= 10;
        if (quo_a == 0) break;
    }
    
    while(true)
    {
        stack_B.push(quo_b % 10);
        quo_b /= 10;
        if (quo_b == 0) break;
    }
    
    while(true)
    {
        if(stack_A.top() == stack_B.top())
        {
            if (stack_A.size() == 1 && stack_B.size() == 1)
                return false;
            if (stack_A.size() > 1)
                stack_A.pop();
            if (stack_B.size() > 1)
                stack_B.pop();
        }
        else
            return stack_A.top() > stack_B.top();
    }
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    if (numbers[0] == 0)
        return "0";
    
    for(auto & elem : numbers)
    {
        answer += to_string(elem);
    }
    
    return answer;
}
  • 그럼에도 불구하고 위 풀이는 프로그래머스의 테스트케이스 1번 ~ 6번을 계속해서 실패했다.
    • 반례는 다름이 아니라 20 & 200 같은 상황이였다! 이런 케이스일 때 내 구현 코드로는 20200 > 20020 이므로 20 > 200인게 명확함에도 불구하고 20 == 200으로 인식 된다.
      • 2 와 2 는 같고 0 과 0 은 같고 또 0 과 0 도 같기 때문에
    • 이런 경우는 어떻게 예외를 두고 처리해야 하나 싶은 막막함에 내 풀이는 폐기하기 되었다 😢


정답 풀이 ⭕

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

using namespace std;

bool compare (int a, int b)
{ 
    string str_a = to_astring(a) + to_string(b);
    string str_b = to_string(b) + to_string(a);
    
    return str_a > str_b;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    if (numbers[0] == 0)
        return "0";
    
    for(auto & elem : numbers)
    {
        answer += to_string(elem);
    }
    
    return answer;
}
  • 두 원소를 비교할 때 그냥 간단하게 두 원소를 문자열로 변환하여 ab, ba 순서로 붙여본 후 이 두개를 문자열 순서로 비교하면 됐다.
    • 문자열로서 앞에 붙였을 때 더 커지는 원소라면 문자열로 변환한 두 원소끼리 붙인 것끼리 비교했을 때도 클 것이니까!
      • 간단한 생각인데 왜 이 생각을 못 했을까 ㅠ ㅠ


이 문제로 배운 점 정리

  • 런타임 에러가 발생하므로 stack.top() 호출 하기 전에 빈 스택이 되는 경우는 없었는지 체크했어야 했다.
  • strict weak ordering. 비교 함수 구현 혹은 비교 연산자 오버로딩시 반드시 서로 다른 원소의 비교 경우에만 true를 리턴해야 한다. <, > ⭕ <=, >= ❌
    • a > b 인 경우에도 true, a == b 인 경우에도 true 이러면 안됨!!
  • 원소들을 문자열로서 전부 붙인 것을 최대로 만드는 정렬이라면 그의 일부분 개념으로서 두 원소끼리 붙인 것에어서의 최대가 되는 원소가 결국엔 전체 정렬에서 앞부분을 차지한다.
  • 문자열 붙이기
    • 처음엔 strcat만 생각했었다. 이는 C 스타일 문자열인 char 배열, char 포인터에만 적용되는 것임에도 불구하고 ㅠ ㅠ
    • C++의 string.h 헤더 파일은 문자열끼리 이어 붙이는 다양한 방법을 제공한다.
      1. + 연산자가 오버로딩 되어 있으므로 문자열끼리 + 연산하면 이어 붙일 수 있다.
      2. append 함수 👉 뒤에 문자열을 붙인다.
      3. insert 함수 👉 문자열의 원하는 인덱스에 문자열을 삽일 할 때


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기

참고