[프로그래머스] 레벨 2 - 가장 큰 수

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

프로그래머스 레벨 2 문제다.

문자열에 대한 정렬함수에 대해 한 번 더 깊이 생각해보게 한 문제다.

기존에는 <algorithm>으로 정수형 변수의 정렬을 많이 다뤘다.

문자열에 대한 정렬도 다룬 적 있지만 모두 길이가 같을 때 사용했었다.

 

이 문제는 길이가 다른 문자열을 '내 입맛에 맞게' 정렬시킬 수 있는 방법을 생각하게한 문제다.

1, 30, 2, 12, 23과 같이 길이가 다른 정수를 '문자열'로 바꿨을 때 앞에서부터 결합하여 가장 큰 수를 나타내는 '문자열'을 만드는 것이 이 문제의 요구사항이다.

 

1. 기존의 sort 함수와 세 번째 인자 greater<자료형>() 또는 less<자료형>()

 

1-1. sort(v.begin(), v.end()) 또는 sort(v.begin(), v.end(), less<string>())

기존의 sort 함수로 위 정수들의 문자열을 정렬하면

'1 12 2 23 30' 의 순서대로 정렬을 시킨다.

즉, 앞자리가 작은 숫자로, 그 수가 같다면 더 짧은 문자열이 나오는 순서로 정렬하는 방식이다. 

이는 문자열이 벡터 v에 저장되어있다고 생각하였을 때 sort(v.begin(), v.end());를 동작시킨 결과다.

sort함수의 디폴트가 오름차순 정렬이므로 sort(v.begin(), v.end(), less<string>())의 결과와 같다.

 

1-2. sort(v.begin(), v.end(), greater<string>())

만약 세 번째 인자에 내림차순을 의미하는 greater<string>()을 삽입하면 어떻게 될까.

그 결과는 30 23 2 12 1 순으로 정렬된다. 

즉, 앞 자리 수부터 더 큰 수를 가진 문자열 먼저 두고, 그 수가 같다면 길이가 더 긴 수를 앞에 배치하는 식으로 동작한다.

 

이에 대해 문자열 정렬을 정리하기 위해 예제 코드를 구현하고 실행해보았다.

먼저 greater<string>()으로 정렬한 코드와 실행 화면이다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
#include <functional>
using namespace std;
 
bool cmp(string &a, string &b) {
    // 앞에서부터 왼쪽먼저 결합한 것이 더 큰 것 순으로 정렬해라
    return (a + b > b + a) ? true : false;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    deque<string> v;
 
    for (int i = 0; i < numbers.size(); i++) {
        v.push_back(to_string(numbers.at(i)));
    }
    //sort(v.begin(), v.end(), cmp);
    sort(v.begin(), v.end(), greater<string>());
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << '\n';
 
    while (!v.empty()) {
        answer += v.front();
        v.pop_front();
    }
 
    if (answer[0] == '0')
        return "0";
 
    return answer;
}
 
int main(){
    vector<int> numbers;
    numbers.push_back(1);
    numbers.push_back(21);
    numbers.push_back(2);
    numbers.push_back(23);
    numbers.push_back(30);
 
    string ans = solution(numbers);
    return 0;
}

greater<string>()을 사용해 내림차순 정렬을 한 결과. 앞 자리 수가 같다면 길이가 더 긴 것이 먼저 온다.

다음으로 less<string>()을 통해 오름차순 정렬을 한 결과다.

less<string>()을 사용해 오름차순 정렬을 한 결과. 앞 자리 수가 같다면 길이가 더 짧은 문자열이 앞에 온다.

즉, 정리하면, 길이가 서로 다른 숫자로 구성된 문자열들은 sort 함수로 정렬할 수 있다.

 

앞에서부터 숫자를 보면서 기준에 따라 오름 차순이면 작은 수부터 앞에 오고, 수가 같지만 길이가 다를 경우 길이가 짧은 것이 먼저 오는게 오름차순 정렬이다.

반대로 내림차순 정렬은 큰 수를 앞자리에 갖는 문자열이 먼저 오면서 길이가 더 긴 문자열이 먼저 정렬되도록 동작한다.

 

2. 사용자 정의 순서 정렬

이 본문의 핵심이다.

사용자는 bool 함수를 설정하여 사용자가 원하는대로 문자열을 정렬할 수 있다. (다른 자료형도 마찬가지)

먼저 이 문제의 코드를 첨부하고 코드의 줄을 따라가며 설명해보겠다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
#include <functional>
using namespace std;
 
bool cmp(string &a, string &b) {
    // 앞에서부터 왼쪽먼저 결합한 것이 더 큰 것 순으로 정렬해라
    return (a + b > b + a) ? true : false;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    deque<string> v;
 
    for (int i = 0; i < numbers.size(); i++) {
        v.push_back(to_string(numbers.at(i)));
    }
    sort(v.begin(), v.end(), cmp);
    
    while (!v.empty()) {
        answer += v.front();
        v.pop_front();
    }
 
    if (answer[0] == '0')
        return "0";
 
    return answer;
}

(목적)

이 문제를 풀기 위해 문자열이 담겨있는 deque에서 내가 원하는대로 정렬하고 싶다.

나는 앞에서부터 정렬된 문자열들을 그대로 이어붙였을 때가 주어진 문자열들의 순서조합 중 가장 큰 수를 나타내는 문자열을 만들고 싶다.

 

이를 위해 단순히 생각해서 내림차순으로 정렬해 문자열을 만든다고 생각해보자.

만약 3000, 300, 30, 3, 21, 20, 1로 정렬된 내림차순 문자열을 그대로 이어붙인다고해서 원하는 답을 얻을 수 있을까?

답은 아니다.

왜냐하면 300030030321201 은 주어진 문자열을 이용해 만들 수 있는 가장 큰 문자열이 아니기 때문이다.

예를 들어 3 바로 다음에 30, 300, 3000이 이어붙여진다면 330300300021201이 가장 큰 문자열이 될 수 있기 때문이다.

 

반대로 오름차순으로 정렬하면? 120213303003000이 되어 역시 원하는 답을 얻을 수 없다.

 

즉, 기존에 알고있던 세 번째 정렬기준인 greater, less로는 절대 답을 얻을 수 없다!

 

이 때 강력한 힘을 발휘하는 것이 바로 사용자 정의 정렬순서 함수를 구현하고 이를 활용해 정렬하는 것이다.

 

코드 9~12줄을 보면 bool 형의 함수가 선언되어있는 것을 볼 수 있다.

그리고 인자로 문자열 두 개가 전달되는 것을 알 수 있다.

가장 중요한 것은 반환하는 11번째 줄인데, 이 뜻은 다음과 같다.

"앞의 문자열에 뒤의 문자열을 이어 붙인것이

뒤의 문자열에 앞의 문자열을 이어 붙인것 보다 더욱 크도록 정렬해라"

 

즉 예를들어 a로 "23"이 전달되고 b로 "32"이 전달되었다고 생각해보자.

이 정렬 기준으로 하면 a+b는 "2332"이고, b+a는 "3223"이기 때문에 ba순서로 문자열이 정렬되는 것이다.

 

이는 곧 전체 문자열을 가장 크게 정렬시키는 방법이 된다.

 

즉, 사용 방법은 bool형 함수와 비교대상인 두 대상을 인자로 넣어주고, 반환형으로 원하는 기준을 만족했을 때 true를, 아닌 경우 false를 반환하도록 return하게 구현하면 된다. sort함수에는 단순히 이 함수의 이름을 넣어주면 된다.

 

만약 이 방법을 모른다면 문자열의 길이를 고려하고, 한 자리 한 자리 다음으로 인덱스를 넘겨가며 힘들게 구현할 것인데 이 방법을 알면 5분도 안돼 다 구현할 수 있다. 매우 유용한 방법이다.

이 방법은 <queue>의 priority_queue에서도 유사하게 활용할 수 있다. 이에 대한 포스팅은 다음 기회에.

(2020. 2. 24 추가 -> sort와 우선순위 큐에 대한 포스팅 추가하였습니다. 오른쪽 링크를 참고해주세요. https://cpp-dev.tistory.com/88)