프로그래머스: 큰 수 만들기

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

프로그래머스

 

문제 접근 방법을 몰라서 답을 보고 이해하는 것도 한참이 걸렸다..

 

참고 코드 : https://mtoc.tistory.com/80

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

위 블로그를 보고 간신히 이해할 수 있었다.

풀이

총 7글자의 단어에서 6글자의 단어를 만든다고 치면, 앞 두글자내에서는 한 글자라도 단어에 포함되어야한다.

 

글자 만들기는 범위가 중요하다.

코드

#include <bits/stdc++.h>

using namespace std;

string solution(string number, int k) {
    string answer = ""; int start=0;
    for(int i=0;i<number.size();i++){ //한글자씩 만든다
        int maxIndex=0; int maxValue=0;
        for(int j=start;j<=k+i;j++){ //글자를 만들어야할 범위
            if(maxValue < number[j]){ //큰 글자, 그 글자의 인덱스 구하기
                maxValue=number[j]; maxIndex=j;
            }
        }
        start=maxIndex+1; //새로운 시작위치
        answer += maxValue; //큰 글자는 더해주기
        if(answer.size()==number.size()-k) break; //끝나면 break;
    }
    return answer;
}