[프로그래머스] 1929 소수 구하기 - Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐⭐
• 문제 유형: Greedy
• 사용 언어: Java 

---

🔍 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한사항

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

💡 풀이 노트

while (!stac.isEmpty() && c > stac.peek() && cnt < k) {
    stac.pop();
    cnt++;
}

Greedy

• 그리디(Greedy) 전략:
• 매 순간 가장 최적인 선택을 하면, 전체적으로도 최적의 결과가 나올 것이라는 전략
• 현재 문자를 `c`라고 할 때, 이전 문자(stac.peek())보다 `c`가 더 크면, 앞으로 더 큰 수를 만들기 위해 지금 peek()을 제거

“앞자리에 더 큰 숫자를 배치하면 최종 결과가 커진다"는 전략을 판단하고 실행

 

풀이

• 숫자를 앞에서부터 한 글자씩 스캔하면서,
• 현재 숫자가 스택의 top보다 크면 이전 숫자를 제거하고 현재 숫자를 넣음
• 이런 방식으로 큰 숫자 위주로 스택에 쌓이게 하여, 결과적으로 가장 큰 숫자 조합 만들기

while (cnt < k) {
    stac.pop();
    cnt++;
}

• 앞에서 모든 숫자를 스캔하고 나왔지만, `cnt < k` → 즉, 아직 다 제거하지 못한 경우
• 예시:

number = "999", k = 2

• 앞 숫자가 전부 같거나 내림차순이면 `c > stac.peek()` 조건이 안 맞아서 아무것도 pop하지 못함
• 이런 경우 스택에는 `[9, 9, 9]`가 그대로 남아 있고,
• 제거 횟수(k)가 남아 있으므로 맨 끝부터 숫자를 제거하는 것이 가장 좋은 선택

---

🚀 코드 (Java)

import java.util.*;
public class Solution {
    public String solution(String number, int k) {
        int cnt = 0; //제거된 숫자의 수
        Stack<Character> stac = new Stack<>();

        for (char c : number.toCharArray()) {
        // 스택이 비어 있지 않고, 현재 숫자가 더 크며, 아직 제거 횟수가 남았다면
            while(!stac.isEmpty() && c > stac.peek() && cnt < k){
                stac.pop(); // 이전 숫자 제거
                cnt++;
            }
            stac.push(c); // 현재 숫자 삽입
        }
        
        // 아직 제거 횟수가 남았다면 뒤에서부터 제거
        while(cnt < k){
            stac.pop();
            cnt++;
        }
        
        StringBuilder sb = new StringBuilder();
        for (char c : stac) {
            sb.append(c);
        }

        return sb.toString();

    }
}

---

🖥 실행 결과

입력 & 출력

number		k	return
"1924"		2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

---

🔄 개선 가능성

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest