[알고리즘/프로그래머스] 가장 큰 수 - C++

오늘도 계속해서 알고리즘 문제를 풀어볼 예정이다.

*본인은 C++로 코딩할 예정이다.

 

---

1. 문제

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

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,

이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때,

순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

출저 - 프로그래머스

2. 사고 - 정렬

1. 매번 가장 크게만들 수 있는 수를 고르면 O(n^2) 시간 복잡도를 가지게 될 것이다.

2. 우선 빈 문자열로 수를 초기화 한다.

3. numbers를 큰 수를 만들 수 있는 순서대로 정렬한다. > O(nlogn)

4. 하나하나씩 answer에 꺼내어 붙인다. > O(n)

5. 시간복잡도는 O(nlogn)을 가지게 된다.

6. 추가적으로 넘어오는 numbers에 0만 여러개 들어있는 경우의 수도 고려한다.

 

- 큰 수 정렬 기준

> 2와 34가 있다고 해보자. 234, 혹은 342가 될 수 있다. 이와 같이 하나씩 붙여보고 대소관계를 파악할 수 있다.

3. 코딩

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

bool cmp(int a, int b) {
	string str_fir;
	string str_sec;
	string s_a = to_string(a);
	string s_b = to_string(b);
	str_fir = s_a + s_b;
	str_sec = s_b + s_a;
	bool res = str_fir > str_sec;
	return res;
}

string solution(vector<int> numbers) {
	string answer = "";
	sort(numbers.begin(), numbers.end(), cmp);
	for (auto &num : numbers) {
		answer += to_string(num);
	}
	
	return answer[0] == '0' ? "0" : answer; //numbers에 0이 여러개면 000... 대비
}

int main(void) {
	vector<int> num;
	num.push_back(6);
	num.push_back(10);
	num.push_back(2);


	cout << solution(num) << endl;

	return 0;
}

- 수 : [6, 10, 2]

- 정렬된 수 : [6, 2, 10]

= 결과 : 6210

4. 알게된 것

예외의 상황을 항상 고려하자.

마지막 테스트케이스에서 삽질을 오래하였는데, 바로 numbers에 0이 여러개 들어온 상황이다.

이런 경우 원래 코드대로라면 000.. 이런식으로 반환할 것이다.

그렇기 때문에 answer의 첫번째 인덱스가 0이면 뒤에 뭐가 오든 0으로 치환시켜버리도록 코딩해야한다.

위와 같이 모든 경우의 수를 고려해야 완벽하게 코딩테스트에서 통과할 수 있을 것이다.

 

---

"야! C++도 sort 함수 있어!"