문제
https://programmers.co.kr/learn/courses/30/lessons/42883
코드
#include <string>
#include <vector>
#include<algorithm>
using namespace std;
string solution(string number, int k) {
string answer = "";
int answerSize=number.size()-k;
while(answer.size()!=answerSize){
string temp=number.substr(0,number.size()-answerSize+1+answer.size());
int index=max_element(temp.begin(),temp.end())-temp.begin();
answer+=*max_element(temp.begin(),temp.end());
number=number.substr(index+1);
}
return answer;
}풀이
그리디 문제로 문자열로된 숫자와 제거해야될 숫자의 개수k를 줍니다. 어떤 숫자를 제거하면 가장 큰 수가 나오는지 구하는 문제입니다.
| number | k | answerSize | return |
|---|---|---|---|
| "1924" | 2 | 2 | "94" |
| "1231234" | 3 | 4 | "3234" |
| "4177252841" | 4 | 6 | "775841" |
문제에서 주는 입출력 예제이고 answerSize는 제가 설명을 하기 위해 추가 했습니다.
제가 세운 로직은 answerSize를 보장해주는 자릿수중에 큰 수를 찾는 겁니다
예를 들어서 "1924"의 경우 1,9,2중에 큰수를 찾아서 제일 앞자리 수로 넣습니다. 만약 3번째 수가 가장 크다고 해도 뒤에 4번째 수가 있기 때문에 answerSize를 만족합니다
"1231234"의 경우 앞의 "1231"중에 큰수를 찾아서 앞자리 수로 넣어줍니다
그 뒤에는 남은"1234"에서 앞에 "12"중 큰 2를 넣어주고 나머지 "34"를 넣어줍니다.
대충 이해가 가시나요 암튼 그렇게 로직을 세웠고 코드는 substr을 사용해서 number을 계속 잘라주면서 while문을 돌렸습니다
