프로그래머스 탐욕법 <큰 수 만들기> [JAVA]

 

문제는 요점은 주어진 숫자 number에서 K개의 숫자를 뺀 수 중 가장 큰 수를 찾아라 입니다.

 

방법1

n의 자릿 수 - k = 가장 큰 수의 길이가 됩니다.

 

예를 들어 "4177252841"이 주어지고 k가 4가 주어져서 결과 값의 자릿수가 6자리라고 했을 때 OOOOOO

 

k개의 숫자를 뺀 결과 값이 가장 큰 수의 첫번째 자리에 올 수 있는 수는 n에서 인덱스가 0~k까지에 해당하는 수 중 가장 큰 수 가 됩니다.

두번째 자리에 올 수 있는 수는 n에서 인데스가 1~k+1에 해당하는 수
세번째 자리에 올 수 있는 수는 n에서 인데스가 2~k+2에 해당하는 수 ...
이런식으로 해당 자리에 오는 수 중 큰 자릿수 순서대로 하나씩 찾는데 그 해당하는 자리 수 보다 앞자리에 올 수 는 없기 때문에 마지막으로 찾은 자리 수의 인덱스 +1 부터 자리에 올 수 있는 가장 마지막 수의 인덱스 까지 비교하며 찾습니다.

 

/**
 * https://programmers.co.kr/learn/courses/30/lessons/42860
 * 코딩테스트 연습
 * 탐욕법(Greedy)
 * 큰 수 만들기
 **/

public class Solution10 {

    public static void main(String[] args) {
        Solution10 solution = new Solution10();
        String num = "111119";
        int k = 3;
        System.out.println(solution.solution(num, k));
    }

    /**
     * 주어진 숫자 n에서 k개의 숫자를 빼서 가장 큰 수를 찾아라
     * n의 자릿 수 - k = 가장 큰 수의 길이
     *
     * 가장 큰 수의 첫번째 자리에 올 수 있는 수는 n에서 인덱스가 0~k까지
     * 두번째 자리에 올 수 있는 수는 n에서 인데스가 1~k+1에 해당하는 수
     * 세번째 자리에 올 수 있는 수는 n에서 인데스가 2~k+2에 해당하는 수 ...
     * 이런식으로 해당 자리에 오는 수 중 가장 큰 수를 하나씩 찾는데 그 전수 보다 앞자리에 올 수 는 없기 때문에
     * 마지막으로 찾은 자리 수의 인덱스 +1부터 자리에 올 수 있는 가장 마지막 수의 인덱스 까지 비교하며 찾는다.
     */
    public String solution(String number, int k) {

        StringBuilder sb = new StringBuilder();
        int idx = 0;
        int max;

        for (int i = 0; i < number.length() - k; i++) {
            max = Integer.MIN_VALUE;
            System.out.println("idx : " + i);
            for (int j = idx; j <= i + k; j++) {
                System.out.println("j :" + j);
                if (max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    System.out.println(max);
                    idx = j + 1;

                }
            }
            System.out.println("comp : " + max);
            sb.append(max);
        }
        return sb.toString();
    }
}

 

방법2

    /**
     * 사람들은 똑똑하다...
     */
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < result.length; i++) {
            sb.append(stack.get(i));
        }

        return sb.toString();
    }

이런식으로 스택에 넣어서 해결하기도 하던데 똑똑한 사람들이 많은거 같습니다