[프로그래머스] 2️⃣ 큰 수 만들기 (java,탐욕법(Greedy))

🔗 문제 링크 

https://school.programmers.co.kr/learn/courses/30/lessons/42883

 

 

---

⛈️  문제 설명 

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

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

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

제한 조건

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

입출력 예

number k return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

---

 

⛈️  풀이 과정

① 각 숫자의 자리를 유지해야하므로 Stack을 이용 

② 스택 상단에 있는 숫자와 현재 숫자를 비교해서 현재 숫자가 더 클 경우 pop하고, 필요시 이를 반복

③ 조건을 만족하지 못한다면 push

④ 지워야 할 k만큼의 수가 충족된 경우, 모두 스택에 집어 넣은 뒤 pop하여 문자열 뒤집기

📍 그러나, 54321 같은 경우, delete 조건이 끝나지 않은 채 for문이 종료됨. 따라서 k 만큼 pop하여 삭제해야함

 

---

 

⛈️  대차게 틀린 코드  😇

import java.util.*;
/*
    숫자의 위치가 변경되면 안되므로 -> Stack을 사용
*/

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        Stack <Character>  st = new Stack<>();
        int delete=0;
        
        char ch[] = number.toCharArray();
        
        st.push(ch[0]);
        for (int i=1; i<ch.length; i++){
            
            // 스택에 내용물이 있다면?
            if (delete ==k ) {
                st.push(ch[i]);
                continue;
            }
            
            else
            {  
                while (st.size()>0 && st.peek()-'0'< ch[i]-'0') {
                    st.pop();
                    delete+=1;
                    
                    if (delete == k ) break;
                }
                st.push(ch[i]);
            }
        }
        
        while (!st.isEmpty()){
            answer+=st.pop();
        }
        
        StringBuilder sb= new StringBuilder(answer);
        answer = sb.reverse().toString();
        
        return answer;
    }
}

k를 충족시키지 않은 채 for문이 끝남 

 

 

 

---

⛈️  풀이 코드

import java.util.*;
/*
    숫자의 위치가 변경되면 안되므로 -> Stack을 사용
*/

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        Stack <Character>  st = new Stack<>();
        int delete=0;
        
        char ch[] = number.toCharArray();
        
        st.push(ch[0]);
        for (int i=1; i<ch.length; i++){
            
            // 스택에 내용물이 있다면?
            if (delete ==k ) {
                st.push(ch[i]);
                continue;
            }
            
            else
            {  
                while (st.size()>0 && st.peek()-'0'< ch[i]-'0') {
                    st.pop();
                    delete+=1;
                    
                    if (delete == k ) break;
                }
                st.push(ch[i]);
            }
        }

        // 남은 숫자를 제거하지 못한 경우 (76544321 인경우 push만 했기에 pop 해줘야함 ) 
        while (delete <k){
            delete++;
            st.pop();
        }
        
        
        while (!st.isEmpty()){
            answer+=st.pop();
        }
        
        StringBuilder sb= new StringBuilder(answer);
        answer = sb.reverse().toString();
        
        return answer;
    }
}

---

 

☀️  한번 더 생각해 보자! 

📍문자열 뒤집기

StringBuilder sb= new StringBuilder(answer);
        answer = sb.reverse().toString();

📍다양한 경우의 수를 생각해보기, for문이 끝날 경우 어떻게 되는지 등 

 

 

결과