일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 백준
- c++
- Gold 4
- Level 2
- BFS
- 구현
- Level 4
- 그리디
- 브루트포스
- 부스트코스
- 삼성 SW 역량 테스트
- 월간 코드 챌린지
- 코드 리뷰
- 2020 카카오 인턴십
- 코드리뷰
- 스택/큐
- DP
- 프로그래머스
- DFS
- Gold 5
- Level 3
- next_permutation
- pass
- 시뮬레이션
- 2019 KAKAO BLIND
- 백트래킹
- 2020 KAKAO BLIND
- Web
- SWEA
- level 1
- Today
- Total
Min:D's Devlog
[프로그래머스][정렬][C++] 가장 큰 수 본문
문제
프로그래머스 정렬 - 가장 큰 수
문제 설명
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" |
문제 풀이
접근 방식
이 문제는 주어진 숫자들을 어떤 순서로 정렬해야 가장 큰 수를 만들 수 있는지를 찾는 문제였다.
답을 찾을 수 있는 방법이 많아서 여러 시도를 많이 해본 문제였다.
첫 번째로 시도한 방법은 순열을 통해 가장 최댓값을 찾는 방법이었다.
next_permutation으로 모든 가능 경우를 찾아서 구하였는데, 시간 초과로 실패하였다..
두 번째로 시도한 방법은 숫자를 변형하여 내림차순으로 정렬하는 방법이었다.
숫자들의 자릿수가 다 다르기 때문에 모두 같은 자릿수로 바꿔주고,
비교 함수를 만들어서 여러 조건을 고려하여 내림차순으로 정렬하고,
그 인덱스에 따라 원래 수를 조합하여 답을 구하였다.
이 방식으로 문제를 해결할 수는 있었으나, 고려해야 할 조건이 많아서 코드가 굉장히 복잡하였다..
좋은 방식은 아닌 거 같아서 더 자세히는 설명하지 않고 코드로 대체하고자 한다..
vector<int> copy_num;
bool cmp(const pair<string, int>& a, const pair<string, int>& b){
if(a.first == b.first){
string ab = to_string(copy_num[a.second]) + to_string(copy_num[b.second]);
string ba = to_string(copy_num[b.second]) + to_string(copy_num[a.second]);
return ab > ba;
}
return a.first > b.first;
}
string solution(vector<int> numbers) {
// 최대값의 자리수(count) 구하기
int count = 0;
int max_num = *max_element(numbers.begin(),numbers.end());
if(max_num == 0)
return "0";
while(max_num > 0){
max_num /= 10;
count++;
}
// 모든 숫자 자리수 맞춰주기(맨 앞의 숫자로 채우기)
int len = numbers.size();
vector<pair<string,int>> ans;
for(int i = 0; i < len; i++) {
ans.push_back(make_pair(to_string(numbers[i]),i));
int size = ans[i].first.size();
for(int j = size; j < count; j++)
ans[i].first += ans[i].first[0];
}
// 정렬 후 원래 배열을 answer에 더해주기
copy_num = numbers;
sort(ans.begin(), ans.end(), cmp);
string answer = "";
for(int i = 0; i < len; i++)
answer += to_string(numbers[ans[i].second]);
return answer;
}
위의 방법보다 더 좋은 방법이 있지 않을까 찾아보고 고민하다 훨씬 간단하고 쉬운 방법을 알게 되었다.
이 방법은 숫자들을 문자열로 바꿔주고, 두 문자열을 합쳤을 때 더 큰 값이 되는 순서대로 정렬하는 방법이다.
이를 위해서 비교 함수를 아래와 같이 구현해주어야 한다.
이 방법으로 문제를 해결하면 아주 쉽고 간단하게 코드를 작성할 수 있다.
또한, 이 방법이 위의 방법보다 2배 정도 빠르다.
bool cmp(const string& a, const string& b){
return a+b > b+a;
}
이 문제를 풀 때 주의해야 하는 경우는 0만 존재하는 경우이다.이 경우에는 00..0이 아닌 0을 리턴해주도록 설정해주어야 모든 테스트 케이스를 통과할 수 있다.
풀이 코드 - C++
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(const string& a, const string& b){
return a+b > b+a;
}
string solution(vector<int> numbers) {
vector<string> number;
int size = numbers.size();
int zero_count = 0;
for(int i : numbers){
number.push_back(to_string(i));
if(i == 0)
zero_count++;
}
if(size == zero_count)
return "0";
sort(number.begin(), number.end(),cmp);
string answer = "";
for(string i : number){
answer += i;
}
return answer;
}
실행 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스][2020 KAKAO BLIND][C++] 외벽 점검 (1) | 2020.08.17 |
---|---|
[프로그래머스][DFS/BFS][C++] 여행경로 (0) | 2020.08.16 |
[프로그래머스][이분탐색][C++] 입국심사 (0) | 2020.07.20 |
[프로그래머스][완전탐색][C++] 소수 찾기 (0) | 2020.07.10 |
[프로그래머스][그리디][C++] 큰 수 만들기 (0) | 2020.07.06 |