[탐욕법(Greedy)] 큰 수 만들기 - JAVA

https://programmers.co.kr/learn/courses/30/lessons/42883?language=cpp 

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

---

허허 이 문제도 이해가 가지 않아서 코드 보고 그려가며 이해했슴다..

 

먼저 구해야 할 문자열의 길이는 전체 문자열에서 k개를 뺀 만큼이 된다

구할 문자열의 길이만큼 for 문을 돌면서 구한다

이 때 바깥 for문은 최대로 돌 수 있는 for문이니까 주어진 문자열의 길이에서 k를 뺀 만큼을 한계로 잡는다

그리고 안쪽 for문에서 가장 큰 숫자를 골라주면 된다

 

...네?

이해가 안가서 그림을 그려보았당

짠!

k가 3이고 전체 문자열의 길이가 7이니까 숫자를 4번 골라주면 된다

그리고 4번 고르는 것에서 첫 시작이 i고 끝이 j가 되는 거다

음.,, 지금 보니까 그림이 좀 이상하긴 한데

저기서 가장 큰 값을 골라주고 그 다음 index부터 반복문을 돌면 된다

아래는 코드!

 

 

 

자바 코드)

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        int index=0;
        int max = 0;

        for(int i=0;i<number.length()-k;i++) {
            for(int j=index;j<=k+i;j++) {
                if(max < number.charAt(j) - '0') {
                    max = number.charAt(j)-'0';
                    index = j+1;
                }
            }
            answer.append(max);
            max=0;
        }
        return answer.toString();
    }
}

이해는 가는데 솔직히 다시 혼자서 짤 자신은... 없다...

그리디 문제.. 프로그래머스 다 풀고 백준에서 좀 더 골라 풀어봐야겠다

빠잉