[고득점Kit][정렬] 가장 큰 수 ⭐⭐
카테고리: Programmers
[정렬] 가장 큰 수
난이도 ⭐⭐
문제
배울게 많은 문제였다!
내 풀이 (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 한다.
- 우선 비교하기에 앞서 자릿수들을 구분한다. 112 는 1, 1, 2 로 12 는 1, 2 로.
- 이렇게 나는 위와 같이 두 수를 비교할 수 있으며 이와 같은 기준으로 정렬하면 될 것이라고 생각했다.
- 붙여 이었을 때 큰 수를 만들 수 있는 것을 기준으로
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()빈 스택에 접근하려고 하니 런타임 에러가 발생하는 것
- 원소가 0 이면
- 🎵 교훈
- 런타임 에러 segmentation fault (core dumped)에러가 발생한다면 빈 컨테이너 혹은 아무것도 없는 null 상태에서 그 빈 인스턴스의 함수를 호출하려고 하진 않는지 그런 경우는 혹시 없는지 검사를 꼭 해야 한다.
- 런타임 에러가 발생하므로 stack.top() 호출 하기 전에 빈 스택이 되는 경우는 없었는지 체크했어야 했다.
- 런타임 에러 segmentation fault (core dumped)에러가 발생한다면 빈 컨테이너 혹은 아무것도 없는 null 상태에서 그 빈 인스턴스의 함수를 호출하려고 하진 않는지 그런 경우는 혹시 없는지 검사를 꼭 해야 한다.
- 아래와 같이 고쳐주었다.
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.
- It sorts only different numbers. You should always use
- 난 같은 경우에도
- 🎵 교훈
- 비교함수를 구현할 땐
<=,>=일 때 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 헤더 파일은 문자열끼리 이어 붙이는 다양한 방법을 제공한다.
+연산자가 오버로딩 되어 있으므로 문자열끼리+연산하면 이어 붙일 수 있다.append함수 👉 뒤에 문자열을 붙인다.insert함수 👉 문자열의 원하는 인덱스에 문자열을 삽일 할 때
- 처음엔
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기