Lv.2 / 큰 수 만들기

문제

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

프로그래머스

---

 

코드

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

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int answerSize = number.size() - k; // 뽑아야하는 숫자의 수
    int idx = 0; // 탐색 위치
    
    while(answer.size() < answerSize) {
        char selected = number[idx]; // 뽑힐 수 
        int maxi = idx; // 뽑힌 수의 index
        int limit = idx + k; // 탐색할 개수
        
        for(int i = idx; i <= limit; i++) {
            if(number[i] > selected) { // 최댓값 갱신
                selected = number[i];
                maxi = i;
            }
        }
        
        answer += selected; // 답에 추가
        k -= (maxi - idx); // 제거한만큼 빼주기
        idx = maxi + 1; // 다음 탐색 위치 지정
        
        if(k <= 0) { // 뺄거 다 빼면 나머지는 그냥 그대로
            while(idx < number.size()) answer += number[idx++];
        }
    }
    
    return answer;
}

---

 

풀이

이번 문제는 아이디어를 생각해내는 것이 매우 어려웠다.

 

우선 구해야하는 answer 의 길이는 전체 number 의 길이에서 k 개를 제거한 만큼이다. 그래서 이만큼 반복을 수행한다.

반복마다

• 뽑히게 될 숫자인 selected
• 뽑히게 될 숫자의 index 를 저장하는 maxi
• 최대 탐색 범위인 limit

3개의 변수를 활용한다.

 

탐색의 시작점인 idx 부터 범위인 limit 까지 돌면서 최댓값을 갱신하여준다.

범위 내 탐색이 끝나면 답인 answer 에 추가해주고 선택된 수의 index 인 maxi 에서 탐색의 시작점인 idx 를 빼주어 답을 위해서 제거된 숫자의 갯수를 k 에서 차감해준다.

idx 에는 다음 탐색의 시작점인 maxi + 1 을 저장해준다.

 

만약 k 가 0 이하라면 남은 숫자의 수는 탐색할 필요 없이 모두 답에 포함해줘야 한다는 뜻이기에 모두 추가해준다.