[프로그래머스] (Java) 큰 수 만들기 (그리디/Greedy)

 

📑 1. 문제설명

---

💡 2. 접근방식

완전탐색은 안되는 이유

• 문제에서 number≤1,000,000으로 최대 백만자리 숫자가 될 수 있다.
•  number 값이 너무 커서 완전 탐색은 현실적으로 불가능하다.
• k는 1 이상 len(number) - 1 이하
• 예를 들어, 숫자가 1,000,000자리라면 최대 999,999개의 숫자를 제거해야 한다. 

왜 그리디 알고리즘을 써야 하는가?

숫자를 한 번만 순회하면서 적절한 숫자를 선택하거나 제거한다. 
숫자가 백만 자리여도 1,000,000번의 비교만 하면 되기 때문에 효율이 좋다.

문제의 핵심 = '앞에서부터 뒤로 큰 숫자 유지'

앞자리부터 순서대로 숫자를 선택하며 큰 숫자를 유지하는 방식으로 풀어야 한다.

나는 이중포문으로 풀었는데 다른 분들이 풀이한 걸 보니 스택을 사용해 더 간단히 구현 가능하다.

접근방식

number.length - k 만큼 반복문을 돌린다. 조건에서 k만큼의 수를 제거했을때 가장 큰 수를 구해야 하기 때문에 리턴할 문자열은 number.length - k 이다.

 

그리고 앞에서부터 각 자리수별로 가장 큰 숫자를 탐색한다. 첫번째 자릿수를 구하고 두번째 for문의 범위는 찾은 숫자의 다음 숫자 index부터 앞으로 이어붙혀야할 문자의 길이 -1을 남기고 그 앞 index까지 탐색을 해야한다. 그래서 index에는 가장 큰수 다음 index를 넣어준다

---

⭐ 3. 정답코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        
        char[] arr = number.toCharArray();
        int len = arr.length - k;
        int index = 0;
        
        for(int i = 0; i < len; i++) {
            char max = '0';
            for(int j = index; j <= i+k; j++) {
                if(arr[j] > max) {
                    max = arr[j];
                    index = j+1;
                }
            }
            sb.append(Character.toString(max));
        }
        answer = sb.toString();
        return answer;
    }
}

(예시)

4177252841는 10자리 숫자이다.

n = 10, k = 4 이기 때문에 n - k = 10 - 4 = 6

6자리의 가장 큰 수를 만들기 위해 맨 앞자리부터 하나씩 탐색을 시작한다.

 

처음에는 (41772 중에 가장 큰 수 탐색) +  52841 이렇게 하는 이유는 뒤에 다섯자리가 남아 있어야 앞에 한 자리를 더해서 6자리가 되기 때문이다. 41772 중에 가장 큰 7이 StringBuilder에 추가된다.

 

두 번째 탐색 범위는 다음 숫자인 7부터이고, 5까지이다. (이어붙일 4자리 숫자 남겨놓은 지점까지가 범위)

그래서 이번에는  (7725) 중 가장 큰 수를 탐색한다.

왜냐하면 7 + (7725 중에 가장 큰 수) + 2841 = > 이렇게 붙여야 6자리가 되기 때문이다.

두 번째 탐색에서도 7이 뽑히기 때문에 탐색이 끝난 현재 StringBuilder에는 77이 추가된다.

 

세 번째 탐색은 그 다음 숫자인 2부터 시작한다. 

77 + (252 중에 가장 큰 수) + 841  이렇게 해서 6자리이기 때문에 775 까지 StringBuilder에 추가된다. 

 

네 번째 탐색은

775 + (28 중에 가장 큰 수) + 41 

결과는 StringBuilder에 7758이 들어간 상태가 된다.

 

다섯번째 탐색은

7758 +  (41) 중에 큰 수이므로 4가 채택된다.

그래서 77584 가 StringBuilder에 추가된다.

 

여섯번째는 남은 숫자가 1개이므로 바로 추가된다. 

👏🏻 좋아요 가장 많이 받은 코드

오호 스택으로 이렇게 푼다구? 

좋은데

import java.util.Stack;
class Solution {
    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);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

 

---

🐦 4. 같은 유형 문제

[프로그래머스] (Java) 체육복 (그리디/Greedy)

[프로그래머스] (Java) 조이스틱 (그리디)

[프로그래머스] (Java) 구명보트 (그리디/Greedy)

[프로그래머스] (Java) 단속카메라 (그리디/Greedy)