[Lv.2] 큰 수 만들기 [프로그래머스_코딩테스트] [Greedy, Stack]

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

프로그래머스

 

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 큰 수 만들기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/42883
    /// </summary>
    public string solution(string number, int k)
    {
        var numberStack = new Stack<char>();
        
        // Greedy + Stack 구조로 해서 결과 도출
        // 핵심 아이디어. 좌측에 나오는 숫자는 제일 큰 숫자가 되어야 가장 큰 숫자가 된다.
        foreach (var numChar in number)
        {
            // 스택에 이전에 넣어진 숫자 (Char)들을 현재 숫자와 비교 후 k를 줄이고 스택에서 빼온다.
            // 해당 스택이 결국 큰 숫자가 되어야 함 
            while (numberStack.Count > 0 && numberStack.Peek() < numChar && k > 0)
            {
                numberStack.Pop();
                k--;
            }
            
            // 현재 나온 숫자를 스택에 넣는다.
            numberStack.Push(numChar);
        }

        // 빼야될 거가 남은 경우 Pop
        while (k > 0)
        {
            numberStack.Pop();
            k--;
        }
        
        // 스택으로 쌓인 것을 뒤집어주는 프로세스
        char[] result = new char[numberStack.Count];
        int index = numberStack.Count - 1;
        
        foreach (var ch in numberStack)
        {
            // 뒤에서 앞으로 채움
            result[index--] = ch;
        }
        
        return new string(result);
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        //var solutions = { { "1924", 2 }, { "1231234", 3}, {"4177252841", 4}};
        Console.WriteLine(sl.solution("4177252841", 4));
    }
}

 

해당 문제는 Greedy 로 해결하는 문제. 일단 필자는 이 문제를 해결하는 방향을 다르게 생각했어서 gpt의 도움을 받아서 해결책을 구했다. 좀 더 2중 반복문이 없이 해결할 방향이 있지 않을까 해서 고민을 거듭하긴 했었으나 필자의 방법은 일단 가장 좌측의 숫자가 가장 큰 숫자가 되어야 완성된 결과값이 제일 큰 숫자가 된다는 것까지였다. 거기서 더 디벨롭을 해서 문제를 해결했어야 하는데 생각외로 거기까지 미치는데 시간이 너무 오래 걸린 관계로 gpt에게 풀이를 도움을 받았던 문제.

 

일단 Stack 구조를 넣는 것은 push와 pop이 빈번히 발생하는 구조이고 마지막에 Reverse를 해줘야 했기에 해당 구조를 사용했다고 한다. 그리고 Greedy 문제의 경우 이러한 Stack이나 리스트 등의 자료구조와 섞어서 해결을 하는 경우가 많다고 하니 잘 공부를 해두려고 한다.

 

 

위 Greedy의 정의에서 볼 수 있듯이 현재 선택시점에 가장 최선의 선택을 내는 것이다.

 

그렇기에 일단 가장 좌측에 가장 큰 숫자가 올 수 있게 하는 것이 가장 최선의 선택이고, 반복문을 돌리면서 가장 최선의 결과가 올 있게 비교를 하는 과정에 포커스를 맞춘다.

 

그래서 number 문자열을 순자적으로 하나씩 돌면서 일단 Stack에 넣기 전에 이전에 Stack에 넣은 가장 최근의 값과 비교를 해서 현재 넣으려는 값보다 작은 경우 Pop을 시키고 난 후, 다시 Stack의 Peek과 현재 값을 비교해서 현재 값이 더 크면 스택에 넣은 것을 뺀다. (그래야 마지막에 Reverse를 시키면 가장 좌측의 숫자가 제일 큰 숫자가 들어가고 연달아 다음 큰 숫자가 배열되는 로직이 될 수 있다.)