[프로그래머스]탐욕법(Greedy) : 큰 수 만들기 (level 2)(c++)

https://programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

방법 1: 탐욕법

#include <string>
 
using namespace std;
 
string solution(string number, int k) {
 
    int size = number.size() - k;
 
    int strt_idx = 0;
    string answer = "";
    /*
        정답 문자열의 i번째 숫자 구하기
        [i - 1번째 숫자의 다음]부터 ~ [뒤에서 size - i번째 이전] 사이를 탐색
        범위 내에서 가장 큰 숫자 = i번째 정답숫자
    */
    for (int i = 0; i < size; ++i)
    {
        int max_idx = strt_idx;
        char max_num = number[max_idx];
        for (int j = strt_idx; j < k + i + 1; ++j)
        {
            if (max_num < number[j])
            {
                max_idx = j;
                max_num = number[j];
            }
        }
 
        // 다음 탐색 범위는 이번 정답 숫자의 다음 인덱스부터
        strt_idx = max_idx + 1;
        answer += max_num;
    }
 
    return answer;
}

 

 

방법 2: 정렬/교환?!

#include <string>
 
using namespace std;
 
string solution(string number, int k) {
 
    /*
        1. A[0 ~ k - 1], B[k ~ size] 두개의 구간으로 number 나누기
        2. A의 맨 뒤에서부터, B의 맨 앞에서부터 비교하기 --> Ai >= Bj 면 교환 
        3. 반복
    */
    for (int i = k - 1; i >= 0; --i)
    {
        for (int j = k; j < number.size(); ++j)
        {
            if (number[i] < number[j])
            {
                break;
            }
            int temp = number[i];
            number[i] = number[j];
            number[j] = temp;
        }
    }
    return number.substr(k);
}

 

 

최악의 경우에서 방법 2가 방법 1보다 확연히 빠르다.

프로그래머스의 풀이를 많이 참고하였다.

 

But... 

for (int i = 0; i < k; ++i)

바깥 for문의 인덱스를 이렇게 두어서

두 구간을 모두 앞에서부터 비교하면 오답이 난다.

이유는 아직 알아내지 못하였다 ㅜㅜ

 

 

TIP

완전탐색으로 풀었는데 시간초과가 난다면?

▶ 그리디를 고려해야 할 때

 

단, 그리디는 최적해를 보장하지 않는다.

그때그때 경우에서의 최적값을 찾아가기 때문에, 

그 결과값이 전체에서 보면 최적해가 아닐 수 있다.

 

따라서 그리디로 문제를 푼다면

이 문제를 그리디로 풀어도 안전할 것이라는 보장!을 증명해야 한다.

 

예를 들어 이번 문제의 경우,

10개의 숫자에서 4개의 숫자를 버려야할 때 = 6개의 숫자만을 선택해야 할때

2번째 숫자는

첫번째 숫자 다음 ~ 맨끝에서 4자리 앞의 숫자의 범위내에

확실히 있을 것이라고 보장할 수 있다.