[프로그래머스] 레벨2 큰 수 만들기

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

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

 

문제 자체의 설명과 코드가 짧은 편이라 해결하고 난 상태에서는 매우 쉬워보였지만, 처음에 생각했을 때에는 무척 헤맸다. 아직 Greedy에 대한 정확한 개념이 부족한 것 같다. 결국 프로그래머스 문제 내의 다른 사람이 올려준 힌트를 참고했다. (https://programmers.co.kr/questions/11211)

어찌어찌 해결하긴했는데 시간복잡도도 아슬아슬할 뿐만 아니라, 다른 사람들의 풀이를 보니 스택을 이용해서 푼 사람들도 있었다. 약간의 혼란스러움을 느낀 문제였다.

 

 

---

문제 및 입출력

 

---

코드

import java.util.Arrays;

class Solution
{
    public String solution(String number, int k)
    {
        // 예외 : 문자 그대로 출력
        if(number.length()==1)
        {
            return number;
        }
        
        StringBuilder sb = new StringBuilder(); // 결과 출력 및 시간초과 방지용
        int window = number.length()-k; // sliding window 크기
        int max = Integer.MIN_VALUE; // 최대값 비교
        int max_index = 0; // 다음 반복문의 sliding window 시작 인덱스
        
        for(int i=0; i<window; i++)
        {
            max = Integer.MIN_VALUE;
            
            for(int j=max_index; j<=k+i; j++)
            {
                // window 내의 최대값과 최대값에 대한 인덱스를 계속 업데이트
                if(number.charAt(j)-'0'>max)
                {
                    max = number.charAt(j)-'0';
                    max_index = j+1;
                }
            }
            
            sb.append(max);
        }
        
        return sb.toString();
    }
}