항해99 22일차 TIL(큰 수 만들기 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

• 한 번에 정답을 도출할 수 있는가 Yes or No
  • No, 숫자 가장 앞에서부터 큰 숫자를 고른다고 해도 안 되고 가장 작은 숫자를 뺀다고 해도 안된다.
• 뺄 수 있는 숫자 다 빼보고 탐색해보기
  • 완전 탐색이라라고 하기엔 시간복잡도에서 걸릴 것 같다
• 다시 2번으로 돌아가기 
  • 한 번에 정답을 도출 할 수 있는가 Yes or No
    • Yes, 탐욕스러운 알고리즘
      정답을 만들어야 할 최소한의 숫자들을 뒤에 남겨놓고 앞에 숫자에서 하나 뽑는다. 그 과정을 반복한다.

ex)
입출력 예2번
{}선택 존         {}도출한 존

{1231}234            {}
{2311}234            {3}
{3112}34              {32}
{1123}4                {323}
{1234}                 {3234}

정답 3234

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        // 그리디 알고리즘
        // 각 자리에서 최고로 높은 수가 나오는 경우를 생각하기
        
        String answer = "";
        StringBuilder answerBuilder = new StringBuilder();

        
        char[] array = number.toCharArray();
        
        int len = array.length - k;
        
        // 문자 비교를 시작하는 인덱스를 나타내는 start 변수 
        int start = 0;

        for(int i =0; i<len; i++){
            char max = '0';
            for(int j = start; j <= i + k; j++){
                // 가장 큰수를 골라서 그 다음 인덱스를 시작 인덱스로 설정하기 
                if(array[j] > max){
                    max = array[j];
                    start=j+1;
                }
            }
            // 가장 큰 문자를 String에 넣어주기
            answerBuilder.append(Character.toString(max));
        }
        
        // k개의 수를 제거할 때 얻을 수 있는 가장 큰 숫자를 구하려 한다 
        answer = answerBuilder.toString();
        return answer;
    }
    
}

배움

• char 숫자를 부등호로 비교할 수 있다
• 그리드 알고리즘 심화