문제 설명
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" |
문제 요약:
정수 배열을 입력 받아 그 안의 수들을 조합해 가장 큰 수가 되는 조합을 문자열로 출력한다.
🤔 생각해야할 점:
- 정수들을 문자열로 바꿔서 합쳐야 원하는 코드를 만들 수 있다.
- 정수의 조합이 최대가 되려면?
- 문자열로 바꿔서 합하면서 크기를 오름차순 정렬해서 비교한다.
- 문자열을 합치면서 더 크게 되는 조합을 선택하도록 비교함수를 만들기
- 배열에 0만 있어서 0만 더하는 경우 0000이 아니라 0 하나만 출력해야하니까 배열에 0만 있어서 0으로 시작하는 경우의 예외처리를 따로 해서 0 하나만 출력되게 한다.
풀이 방법:
- 입력받은 정수들이 들어 있는 벡터
numbers의 정수들을 문자열로 벡터로 바꿔준다. - compare 함수를 사용해서 문자열 a, b에 대해 a+b 와 b+a 중 더 값이 큰 것을 반환해서 정렬
- 정렬된 순서대로 answer 문자열에 추가해서 답을 출력한다.
sort를 사용한 코드
#include <string>
#include <vector>
#include<algorithm>
using namespace std;
bool compare(string a, string b){
return a+b > b+a;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> num;
for(int n : numbers){
num.push_back(to_string(n));
}
sort(num.begin(),num.end(), compare);
if(num.at(0) == "0"){
return "0";
}
for(string s: num){
answer += s;
}
return answer;
}🌟정수 벡터를 한 요소씩 문자열로 변환해서 문자열 벡터 num에 넣기
for(int n : numbers){
num.push_back(to_string(n));
}🌟 compare 함수를 사용해 오름차순 정렬한다. 2개의 요소를 비교해서 더 큰게 뒤로 가도록 정렬하는데 compare함수에서 2개의 요소를 더해서 이어붙였을 땡 더 큰 쪽이 반환되도록 했다.
a+b와 b+a를 비교하여 true 또는 false 를 반환
a+b 가 b+a 보다 크다면 true 를 반환하고, 그렇지 않다면 false 를 반환
bool compare(string a, string b){
return a+b > b+a;
}🌟 예외 처리
문자열이 00000인 경우 0000이 아닌 0이 출력되어야 한다. 문자열이 더해서 큰 값이 되도록 정렬했기 때문에 0으로 시작한다면 0000인 경우를 의미한다.
→ 0으로 시작하는 경우 0을 반환해서 예외 처리
if(num.at(0) == "0"){
return "0";
}🌟 문자를 문자열에 추가해서 반환
for(string s: num){
answer += s;
}sort를 사용하지 않은 코드( bubble sort)
🔴 시간초과
//sort 를 사용하지 않고 직접 버블 정렬을 구현
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(string a, string b){
return a+b > b+a;
}
void bubbleSortPhase(vector<string>& a, int last)
{
for (int pos = 0; pos < last; ++pos) {
if (!compare(a[pos], a[pos + 1])) {
string temp = a[pos];
a[pos] = a[pos + 1];
a[pos + 1] = temp;
}
}
}
void bubbleSort(vector<string>& a)
{
int n = a.size();
for (int i = n - 1; i > 0; --i) {
bubbleSortPhase(a, i);
}
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> num;
for(int n : numbers){
num.push_back(to_string(n));
}
bubbleSort(num);
if (num[0] == "0") {
return "0";
}
for(string s: num){
answer += s;
}
return answer;
}아..버블 정렬 코드가 젤 구현하기 쉬워서 버블 정렬로 문자열을 정렬했더니 테스트 케이스 시간초과다. 그래서 챗지피티에게 물어보니까 버블 정렬의 시간복잡도는 O(n^2) 이고 cpp의 sort의 시간 복잡도는 O(nlogn)이다.
해결→ 같은 nlogn의 시간 복잡도를 가지는 merge 정렬을 사용해보자
merge sort를 사용해 구현한 코드 (🟢 통과)- 챗지피티 사용
//merge sort로 정렬 구현
//시간복잡도 O(nlogn) ->통과
#include <string>
#include <vector>
using namespace std;
// 두 문자열을 결합하여 비교하는 함수
bool compare(string a, string b) {
return a + b > b + a; // 더 큰 값을 반환
}
// 두 부분 배열을 병합하는 함수
void merge(vector<string>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 왼쪽 부분 배열의 길이
int n2 = right - mid; // 오른쪽 부분 배열의 길이
vector<string> L(n1), R(n2); // 임시 배열 생성
// 왼쪽 부분 배열 복사
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
// 오른쪽 부분 배열 복사
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
// 두 부분 배열을 병합하여 정렬
while (i < n1 && j < n2) {
if (compare(L[i], R[j])) // 두 문자열을 비교하여 정렬 순서 결정
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
// 남은 요소들을 복사
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
// 합병 정렬을 수행하는 함수
void mergeSort(vector<string>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 중간 지점 계산
mergeSort(arr, left, mid); // 왼쪽 부분 배열을 정렬
mergeSort(arr, mid + 1, right); // 오른쪽 부분 배열을 정렬
merge(arr, left, mid, right); // 정렬된 부분 배열을 병합
}
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> num;
for (int n : numbers) {
num.push_back(to_string(n));
}
// 합병 정렬을 이용하여 정렬
mergeSort(num, 0, num.size() - 1);
for (string s : num) {
answer += s;
}
if (num[0] == "0") {
return "0";
}
return answer;
}merge sort에서 중요한 구현
- 배열을 반씩 분할해서 비교해 정렬하된 결과를 다시 병합하는 함수
→mergeSort - 분할된 배열을 임시 배열(추가적으로 생성된 공간에) 복사한 후
병합하여 정렬하는 함수 →merge
🌟 merge함수
합병 정렬의 핵심 로직, 추가적인 공간에 복사되어 정렬된 두 개의 부분 배열을 하나의 정렬된 배열로 병합
🌟mergeSort 함수
- 재귀적으로 반복해서 배열을 반씩 나누고 merge 함수를 호출해 정렬 후 다시 병합한다.
