탐욕법(Greedy) > 큰 수 만들기

문제설명

 

---

아... 안녕하세요 똥멍청이고요..

제 풀이과정은... 이번에도 실패했습니다....

또 다른 사람 풀이를 봤습니다

 

1) 첫번째 시도

만들 수 있는 모든 경우의 숫자를 만들어서 배열에 저장 -> 그 중 최댓값 찾기

중간에 고민해봤는데 경우의 수가 너무 많고, 모든 경우의 수를 반복문으로 만드는 과정이 생각보다 어려워서 패스,,,ㅠ

 

2) 구글링

결국 구글링해서 다른 사람 풀이를 봤다

다 이해는 갔다

만들 문자열의 길이는 number.length( )-k 고, 순서는 고정이니까 앞에서 선택할 수 있는 숫자 들 중 큰 수를 골라가는 과정을 하면 된다

그래서 고민한게 당연히 이중 반복문 써야되고 첫번째 반복문은 answer의 길이만큼 반복, 즉 첫번째 반복문에서 iterator는 answer의 인덱스가 되는거지

i=0이면 answer[0]을 찾는 과정의 반복문이 되는거야 ㅇㅋ?

그럼 여기서 중요한건 내부 반복문이 어디부터 어디까지 돌아야되는거냐는거지

안의 반복문은 이전에 선택한 숫자의 다음 자리부터 뒤에 꼭 남겨야되는 자릿수까지 도는거지

예를 들어 4177252841에서 k=4다 -> 6자리 최대 숫자 만들기!

그리고 현재 i는 2야

그니까 answer[2]를 찾는거지 (6자리니까 answer[5]까지 골라야돼)

여기서 안의 반복문 iterator가 j면 j는 선택된 앞자리 수의 다음 index부터 뒤에 최소 3개는 남아야돼 -> 6자리니까!

그럼 j는 i+k 인덱스까지 선택이 가능해! 그래야 뒤에 3개는 남으니까

이거 이해하는데 되게 오래걸렸어,,,, 사실 아직도 아리까리해

이해는 가는데 내가 스스로 생각해낼 수 있을지는 의문이야

 

내가 참고한 블로그 설명임

암튼 이거 이해하니까 뒤에 짜는건 쉽더라고

아래는 작성한 코드야

 

 

---

[ C++ 코드 ]

 

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int index = -1; //선택된 number의 인덱스
    
    for(int i=0; i<number.length()-k; i++) //answer의 index
    {
        char max = 0;
        for(int j=index+1; j<=k+i; j++)
        {
            if(max < number[j])
            {
                max = number[j];
                index = j;
            }
        }
        answer += max;
    }
    
    return answer;
}

이건 반복문 조건 찾는게 나한텐 너무 어려웠던 문제다,,,

좀 더 노력하자 ㅠ_ㅠ