[프로그래머스] 가장 큰 수 (C++)
📌 참고
교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers
코딩테스트 고득점 Kit > 정렬
문제풀이 (2022-01-21 FRI 💻)
🤔 사담 + 🚨 간과 또는 실수한 부분
처음에는 쉽게 순열을 활용해서 풀면 되겠꾼! 했는데 시간초과가 나버렸다..
순열은 사실 상 가능한 모든 경우의 수를 다 만들어서 확인하는 것이기 때문에
굉장히 비효율적..이라고 할 수 있다 💧
그래도 오랜만에 순열 로직 복습해서 유의미한 시간이었다 (?)
뭔가 아까워서 아래 코드에 주석처리 해두었다
⭕ 물론 C++ algorithm 헤더에 포함된 next_permutation으로 순열을 구할 수도 있다
⭐ 풀이의 핵심
시간 초과를 해결할 방법을 찾지 못하여
구글링을 통해 다른 분들의 코드를 좀 참고하여 수정을 진행했다
👉 사용자 정의 cmp 함수를 만들어서 sort에 정렬 기준으로 넣어주는 방식을 찾았다
cmp 함수의 경우 string 두 개를 비교하는데
두 string을 이어붙이는 두 가지 방법 중 더 큰 것을 반환하도록 하면 된다
ex) string "7"과 string "31"을 이어붙이는 경우,
"7"+"31" = "731"</span> 이 "31" + "7" = "317" 보다 크므로 "731"이 반환된다
👉 한 가지 유의할 점은 string 형의 숫자를 비교하는 작업이기 때문에
numbers 원소 중 0이 가장 큰 숫자 (+numbers의 길이가 2 이상) 일 때
- numbers의 길이는 1 이상 100,000 이하입니다.
- numers의 원소는 0 이상 1,000 이하입니다.
라는 조건에 따라 answer는 '00', '000'과 같은 요상한 (?) 값이 될 수 있기 때문에
answer = '0' 으로 answer 값을 적절히 바꿔줘야 한다
ex) vector<int> numbers = { 0, 0, 0 } 일 경우 answer가 "000"이 될 수 있음
🔽 코드 (C++)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const string &x, const string &y) {
return x+y > y+x;
}
string solution(vector<int> numbers) {
string answer = "";
int N = numbers.size();
// string으로 변환
vector<string> strings;
for (int i=0; i<N; i++) {
strings.push_back(to_string(numbers[i]));
}
// 정렬 (cmp 함수 : 숫자 두 개씩 이어붙인 값 비교)
sort(strings.begin(), strings.end(), cmp);
// 정렬한 순서대로 숫자 이어붙여서 answer 값 구하기
for (int i=0; i<N; i++) {
answer += strings[i];
}
// 주어진 numbers에서 가장 큰 값이 0인 경우 answer = '0' 처리
if (answer[0] == '0') {
answer = '0';
}
return answer;
}
/* cf) permutation 활용 시 시간 초과
vector<string> candidates;
void permutation(vector<string> strings, int depth, int n) {
if (depth == n) {
string s = "";
for (int i=0; i<n; i++) {
s += strings[i];
}
candidates.push_back(s);
}
else {
for (int i=depth; i<n; i++) {
swap(strings[depth], strings[i]);
permutation(strings, depth+1, n);
swap(strings[depth], strings[i]);
}
}
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> strings;
int N = numbers.size();
for (int i=0; i<N; i++) {
strings.push_back(to_string(numbers[i]));
}
permutation(strings, 0, N);
sort(candidates.begin(), candidates.end(), greater<>());
answer = candidates[0];
return answer;
}
********************************/
Author And Source
이 문제에 관하여([프로그래머스] 가장 큰 수 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dianestar/프로그래머스-가장큰수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)