[프로그래머스/Level 2] 큰 수 만들기 (C++)

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

코딩테스트 연습 - 큰 수 만들기

 

처음에 DFS로 접근했는데, 입력값의 최대 범위가 1000000이라서 시간 초과가 나는 것 같다.

결국 해결하지 못해서 구글 검색을 통해 풀이를 찾아봤는데, 그리디 문제는 도대체 어떻게 생각하면 이런 풀이를 스스로 해낼 수 있는지 아직 감이 안온다. (많이 풀면 되려나 ㅠ)

 

number가 4177252841 이고 k가 4일 때,

1. 첫번째 탐색 : i = 0, 탐색 범위 :  j = 0 ~ 4(0+4), maxNum = 7, maxIdx = 2, start = 3(2+1), answer = 7

2. 두번째 탐색 : i = 1, 탐색 범위 : j = 3 ~ 5(1+4), maxNum = 7, maxIdx = 3, start = 4(3+1), answer = 77

3. 세번째 탐색 : i = 2, 탐색 범위 : j = 4 ~ 6(2+4), maxNum = 5, maxIdx = 5, start = 6(5+1), answer = 775

4. 네번째 탐색 : i = 3, 탐색 범위 : j = 6 ~ 7(3+4), maxNum = 8, maxIdx = 7, start = 8(7+1), answer = 7758

5. 다섯번째 탐색 : i = 4, 탐색 범위 : j = 8 ~ 8(4+4), maxNum = 4, maxIdx = 8, start = 9(8+1), answer = 77584

6. 여섯번째 탐색 : i = 5, 탐색 범위 : j = 9 ~ 9(5+4), maxNum = 1, maxIdx = 9, start = 10(9+1), answer = 77841

 

이런식으로 큰 수를 만들어 낼 수 있다.

 

#include <string>
#include <vector>
using namespace std;

string solution(string number, int k) {
    string answer = "";

    int numSize = number.size() - k; // 정답이 될 길이 (문자열의 길이 - 뺄 숫자의 수)
    int start = 0; // 처음 시작 위치이면서 숫자를 빼고난 후 다시 갱신된 시작 위치
    for(int i = 0; i < numSize; i++) {
        char maxNum = number[start]; // 가장 큰 수를 저장할 변수
        int maxIdx = start; // 가장 큰 수의 인덱스를 저장할 변수
        for(int j = start; j <= i + k; j++) { 
            if(maxNum < number[j]) {
                maxNum = number[j]; // 최대값 갱신
                maxIdx = j;
            }
        }
        start = maxIdx + 1; // 시작 위치 갱신
        answer += maxNum;
    }

    return answer;
}