[프로그래머스] 정렬 문제풀이 1 - 가장 큰 수

문제

 

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

 

문제 해결 방법

 

1. 빈 문자열로 수를 초기화한다.

2. 가장 크게 만들 수 있는 수를 고른다.

3. 그 수를 현재 수에 이어 붙인다.

4. 모든 수를 다 사용할 때까지 반복한다.

 

 

예제 적용

[3, 30, 34, 5, 9]	""
[3, 30, 34, 5]	"9"
[3, 30, 34]	"95"
[3, 30]	"9534"
[30]	"95343"
[]	"9534330"

-> O(N^2) 복잡도

--> 더 나은 해결방법 : sort 적용해보기

 

 

더 나은 문제 해결 방법

 

1. 빈 문자열로 수를 초기화한다.

2. 수의 목록을 (크게 만드는 것 우선으로) 정렬한다. -> O(NlogN)

3. 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.

4. 모든 수를 다 사용할 때까지 반복한다.

 

"크게 만드는 수"의 기준 -> 커봐야 1000이하라고 했으니 4자리만 비교한다

34  3434|34...

vs

343 3433|43....

 

 

알고리즘 설계 -> 구현

 

- 대소 관계 비교를 위한 기준 마련

- 기준을 통해 주어진 배열 정렬

- 정렬된 배열을 이용하여 문자열 표현 완성

 

---

코드 (테스트케이스 1개 통과X)

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

using namespace std;

// 정렬의 기준 판단
bool cmp(int a, int b){
    string s1 = to_string(a) + to_string(b);
    string s2 = to_string(b) + to_string(a);
    return s1 > s2;
}

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

 

위 코드는 대부분의 테스트 케이스를 통과하는데 딱 하나의 케이스를 통과하지 못한다. 바로 "00" 과 같이 numbers가 전부 0으로 이루어진 문자열일 경우 깔끔하게 "0" 이 출력되는 것이 아니라 "000"과 같이 잘못된 답안이 출력되기 때문이다. 따라서 마지막 return문을 약간 수정했다.

 

 

최종 코드 C++

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

using namespace std;

// 정렬의 기준 판단
bool cmp(int a, int b){
    string s1 = to_string(a) + to_string(b);
    string s2 = to_string(b) + to_string(a);
    return s1 > s2;
}

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), cmp);
    for (auto& i : numbers) {
        answer += to_string(i);
    }
    return answer[0] == '0' ? "0" : answer;
}

 

드디어 만점!

 

 

시간 복잡도

 

bool cmp(int a, int b){
    string s1 = to_string(a) + to_string(b);
    string s2 = to_string(b) + to_string(a);
    return s1 > s2;
}

위 함수는 문자가 몇개든 시간 복잡도에 영향을 주지 않는다.

 

sort(numbers.begin(), numbers.end(), cmp);

해당 함수는 O(NlogN)의 시간이 소요된다. 사실, 순서 관계에 따라 원소 N개인 배열을 정렬하는 데에는 O(NlogN)보다 더 낮은 복잡도를 가진 알고리즘은 없다. 

 

for (auto& i : numbers) {
     answer += to_string(i);
}

for 순환문은 N에 비례하는 복잡도 O(N)를 가진다. 

 

--> 전체 solution 함수의 복잡도는 O(NlogN)이다.