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

문제 소개

큰 수 만들기 - 프로그래머스 문제를 다른 방식으로 정리합니다.
이 문제는 숫자에서 k개의 수를 제거해 만들 수 있는 가장 큰 수를 구하는 문제입니다.

이전 포스팅에서는 Deque와 StringBuilder를 사용하는 풀이를 정리했지만,

이번에는 추가 자료구조 없이 char[]만으로 구현한 방식으로 정리했습니다.
문제 링크: 큰 수 만들기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 앞자리부터 숫자를 하나씩 보며 현재 숫자가 이전 숫자보다 크면 이전 숫자 제거
2. 이런 식으로 앞자리에 큰 수가 오도록 구성
3. k개의 수를 제거한 뒤 남은 숫자 중 앞에서부터 필요한 자릿수만큼 반환

---

해결 과정 및 코드

핵심 아이디어

1. 숫자를 왼쪽에서부터 하나씩 탐색하면서 result[]에 저장
2. 지금 들어올 숫자 ch가 앞에 있는 숫자보다 크다면, 앞 숫자를 제거하고 현재 숫자를 채움 (idx 이동)
3. 이런 방식으로 항상 앞자리에 큰 수가 남도록 구성
4. 필요한 숫자 수는 number.length() - k이므로, 해당 길이만큼만 result[]에 채움
5. 최종적으로 char[]를 String으로 변환해 정답 반환

코드

시간 복잡도 : O(N)

public String solution(String number, int k) {
    int len = number.length();
    char[] result = new char[len - k]; // 결과 길이
    int idx = 0;

    for (int i = 0; i < len; i++) {
        char ch = number.charAt(i);

        // 뒤에 있는 값보다 큰 수가 들어오면 앞자리 제거
        while (idx > 0 && result[idx - 1] < ch && k > 0) {
            idx--;
            k--;
        }

        // 필요한 자릿수만큼만 채우기
        if (idx < result.length) result[idx++] = ch;
    }

    return new String(result);
}