1.문제
2. 접근/체크포인트
- 주어진 숫자를 한 자리수로 바꿔서 풀이하는 것이 아니라,주어진 숫자 그대로 순서만 변경.
ex) {10, 2, 45} > 45210- 비교하는 과정에서 시간 초과 주의 (numbers의 길이는 1이상 100,000이하)
3. 해결 방법
- int형 vector numbers를 string으로 변환 후 새로운 벡터(sv)에 추가.
- sv벡터의 원소를 비교하여 더했을 때 더 큰 수를 만드는 순서대로 정렬
2-1. 정렬 기준(두 문자열을 더했을 때 더 큰 수가 되는 순서대로 정렬)을 위한 cmp함수 정의
2-2. 정렬 후 sv의 첫 번째 원소가 "0"일 경우, "0" 리턴 (가장 큰 수가 0일 경우)- 내림차순으로 정렬된 sv벡터의 원소를 순서대로 answer에 더해준다.
4.전체코드
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(const string &a, const string &b){
//a+b가 b+a보다 클 경우 a를 앞으로 정렬
return a+b > b+a;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> sv;
//numbers의 원소를 string으로 바꿔서 새 vector에 할당.
for(int i=0; i<numbers.size(); i++){
sv.push_back(to_string(numbers[i]));
}
//cmp 함수를 기준으로 sv 정렬
sort(sv.begin(), sv.end(), cmp);
for(int i=0; i<sv.size(); i++){
answer+=sv[i];
}
if(sv[0] == "0"){ //혹은 answer[0] == "0"
return "0";
}
return answer;
}
5. 참고사항
👉 C++의 sort()함수 사용법
0. 공통 : sort() 함수를 사용하려면 algorithm 헤더 파일을 include 한다.
#incldue<algorithm>1. 기본형 : sort(시작 주소, 마지막 주소+1); -> 오름차순 정렬
ex) vector v = {1,4,53,23,67};
sort(v.begin(), v.end()); -> {1,4,23,53,67} 로 정렬됨.2. 기본형 : sort(시작 주소, 마지막 주소+1, greater<>()); -> 내림차순 정렬
ex) vector v = {1,4,53,23,67};
sort(v.begin(), v.end(), greater<>()); -> {67,53,23,4,1} 로 정렬됨.3. 정렬 기준 정의 : sort(시작 주소, 마지막 주소+1, compare); -> compare()함수에 따라 정렬
💡 compare() 함수의 기본 형태
bool 함수이름 (const 변수형& a, const 변수형& b){ return (a가 b보다 앞에 올 조건); }💡 다양한 compare() 함수 형태
bool cmp(pair<int, int> a, pair<int, int> b) { if(a.first == b.first) //parit의 첫 번째 원소가 같다면 return a.second < b.second; //두 번째 원소를 기준으로 오름차순 정렬 else return a.first < b.first; //첫 번째 원소가 다를 경우, 첫 번째 원소를 기준으로 오름차순 정렬 }ex) compare()함수 예시 : 10으로 나눈 나머지가 작은 순서대로 정렬
bool cmp (const int& a, const int& b) //주소를 매개변수로 받음 return (a%10) < (b%10); //여기는 a가 더 앞으로 정렬 될 조건을 적어줌 (10으로 나눈 나머지가 더 작은 수가 앞으로 정렬) vector<int> v = {10, 45, 72, 28, 9}; sort(v.begin(),v.end(),cmp); //정렬 결과 : {10, 72, 45, 28, 9}
- compare() 함수는 sort() 함수의 세 번째 인자로, 정렬 조건을 정의한 함수이다.
- compare() 함수 대신 수식을 세 번째 인자로 넣을 수도 있다.(결과가 1 or 0이 나올 경우)
- 정렬 된 상태에서 인접한 값을 비교해보면 compare() 함수를 호출 했을 때 참인 경우로 정렬되어있음을 확인할 수 있다. 예를 들어, 위의 예시에서는 compare(10,72), compare(72,45),,,compare(28,9)가 모두 참이다.
- sort()함수의 매개 변수로 compare()함수를 넣을 때, 괄호()는 붙이지 않음.
- coompare() 함수의 이름, 매개변수의 자료형 등은 자유롭게 변형 가능.
6.다른 방법으로 풀어보기
생략
7. 후기
처음에는 문제를 잘못 이해해서 숫자를 전부 한자리수로 바꿔서 제일 큰 수를 만들어서 실패,,,
그 다음 문제를 제대로 이해하고나서는 주어진 수를 이용한 모든 조합을 구한 뒤, 수들의 대소비교를 통해 answer를 찾으려고 했으나 시간초과로 실패,,,
결국 구글링 중 sort() 함수에서 정렬 기준을 직접 정할 수 있다는 사실을 알게되었다.
주어진 수들을 문자열로 바꾸고, 두 개씩 비교해서 가장 큰 수를 만드는 순서로 정렬하는 cmp 함수를 만들어서 구현하였다.
하지만 마지막 test case에서 계속 실패가 떴는데, 원소가 1개, 0일 경우의 처리를 안해줬었다.
다시 if(sv[0] ==0)~ 코드를 추가했는데도 계속 실패,,, 알고보니 문자열로 리턴해야하는데 계속 return 0을 하고 있었다;;
처음에는 간단한 문제라고 생각했는데 생각보다 이런 저런 조건을 계속 놓쳐서 오래 걸렸던 문제.
정신차리자😭 다음에는 파이썬으로 풀어볼 예정!
Frontend-Devloper