[level 2] 큰 수 만들기 - 그리디

첫번째 코드

// number 10^6
// min 원자를 찾고, 
// 앞에서부터 차례대로 min==number[i]이면 제외, 하고 count- 한다
// 그다음 min++하여 count==0이 될때까지 반복 

using System;
public class Solution {
    
    public string solution(string number, int k) {
        // find min [v]
        int min = 9;
        foreach(char num in number){
            int inum = num-'0';
            min = Math.Min(min,inum);
        }
        while(k!=0){
            for (int i=0; i<number.Length; i++){
                int inum = number[i]-'0';
                if (min==inum) {
                    // string remove
                    number = number.Remove(i,1);
                    if (--k == 0){
                        break;
                    }
                }
            }
            min++;
        }
        
        return number;
    }
}

테스트 3
입력값 〉	"4177252841", 4
기댓값 〉	"775841"
실행 결과 〉	실행한 결괏값 "477584"이 기댓값 "775841"과 다릅니다.

풀이를 보고 다시 생각

스택을 활용한 풀이를 참고해서 다시 풀었다.

// 42883
// number 10^6
// min 원자를 찾고, 
// 앞에서부터 차례대로 min==number[i]이면 제외, 하고 count- 한다
// 그다음 min++하여 count==0이 될때까지 반복 
// -------------------- 틀림
// 높은 자릿수의 값이 큰 게 포인트인데, 최소값부터 지우다보면 낮은 자릿수에서 이미 k를 다 소모해 높은 자릿수를 제대로 남길 수 없다. -> 최솟값을 하나씩 제외하면 가장 큰 값이 된다는 가정이 잘못되었음

// 풀이: 스택을 활용한 그리디 알고리즘
// 앞자리는 항상 큰 수, 앞에서부터 진행하면서 뒤에 더 큰 숫자가 나오면, 앞의 숫자를 제거
// 스택을 활용해서 현재 더 큰 숫자와 바로 직전의 숫자를 비교할 수 있다.

// 앞자리 숫자부터 순회, 현재 숫자와 스택 top과 비교한다. 
// curr > top 일때, top은 작은 숫자라서 스택에서 pop -> 이걸 반복하여 최대한 큰수를 높은 자릿수에 배치하도록한다.
// (스택 아래 -> 높은자릿수)
// !(curr > top) 이면 스택에 push

// 현재 top이 높은숫자라면 뒤에 그보다 낮은 숫자는 push될거고 그 다음 들어올수는 지금 들어온 수와 비교하게 될것이다.
// 즉, 계속해서 바로 삽입 직후, 뒤에 더 큰 숫자가 나오면 언제든지 제거될 수 있는 것

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution {
    
    public string solution(string number, int k) {
        Stack<char> stack = new Stack<char>();
        
        for (int i=0; i<number.Length; i++){
            char num = number[i];
            while(stack.Count != 0 && stack.Peek() < num && k > 0){
                stack.Pop();
                k--;
            }
            stack.Push(num);
        }
        
        // k가 양수이면, 제거할것이 남음. 뒤에는 계속 작은수나 같은수가 남아있기 때문에 뒤에서 제거
        while(k>0){
            stack.Pop();
            k--;
        }
        
        char[] answer = stack.ToArray();
        Array.Reverse(answer);
        return new string(answer);
    }
}