[알고리즘] 프로그래머스 42748, 42746

은개·2025년 2월 21일

[CS] 알고리즘

목록 보기

6/21

프로그래머스 42748 - K번째 수

정답

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for (auto command : commands) {
        int start = command[0] - 1;
        int end = command[1];
        int index = command[2] - 1;
        
        // array의 특정 범위를 복사
        vector<int> _array(array.begin() + start, array.begin() + end);
        
        // 복사한 걸 정렬
        sort(_array.begin(), _array.end());
        
        answer.push_back(_array[index]);
    }
    
    return answer;
}

💡

특정 범위 iterator 사용하기
begin() + 시작 인덱스, begin() + 끝 인덱스 + 1을 하면 됨

다른 사람 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;

    for (int i = 0; i < commands.size(); i++) {
        vector<int> temp = array; // 깊은 복사 발생
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        answer.push_back(temp[commands[i][0] + commands[i][2] - 2]);
    }

    return answer;
}

💡

vector는 깊은 복사가 일어남

프로그래머스 42746 - 가장 큰 수

오답 (93/100)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 1. 원소 정렬
// 1-1. 앞자리부터 비교,,, 근데 자리수가 다른 두 수의 앞자리를 어케 비교하지
// 1-2. 앞자리부터 큰 순서대로 내림차순 정렬

// 걍 두 수를 합쳐봤을 때 더 큰 거 기준으로 맨 앞에 정렬하면 됨
bool compare(int a, int b) { // true면 정렬된 상태로 간주, false이면 정렬    
    string tmp1 = to_string(a) + to_string(b);
    string tmp2 = to_string(b) + to_string(a);
    
    return stoi(tmp1) > stoi(tmp2);
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    for (int n : numbers) {
        answer += to_string(n);
    }
    return answer;
}

💭 원인
numbers의 원소가 모두 0일 때, 그냥 "0"을 출력 해야하는데 0을 여러개 출력하기 때문
ex) [0, 0, 0] ➡️ "000" ❌, "0" ⭕️

정답

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 1. 원소 정렬
// 1-1. 앞자리부터 비교,,, 근데 자리수가 다른 두 수의 앞자리를 어케 비교하지
// 1-2. 앞자리부터 큰 순서대로 내림차순 정렬

// 걍 두 수를 합쳐봤을 때 더 큰 거 기준으로 맨 앞에 정렬하면 됨
bool compare(int a, int b) { // true면 정렬된 상태로 간주, false이면 정렬    
    string tmp1 = to_string(a) + to_string(b);
    string tmp2 = to_string(b) + to_string(a);
    
    return stoi(tmp1) > stoi(tmp2);
}

string solution(vector<int> numbers) {
    string answer = "";
    
    sort(numbers.begin(), numbers.end(), compare);
    
    if (numbers[0] == 0) return "0";
    
    for (int n : numbers) {
        answer += to_string(n);
    }
    
    return answer;
}