프로그래머스 - 큰 수 만들기 (문자열 그리디)

 

이 문제는 첫자리수가 가장 큰 수 << 가 키 포인트가 되는 문제임으로.

전체를 돌아가면서, 방금전 확인한 숫자와 지금 확인한 숫자의 크기 차이를 확인하며 앞에서부터 전체를 돌며 k--;

그럼에도 k 가 남는다면 이미 앞쪽은 조건에 맞게 최적의 숫자만 남았기 때문에 뒤에서부터 k만큼 제거.

의 방식으로 풀면된다.

 

이전 비슷한 문제를 풀어본 경험이 있어서 비교적 빨리 풀 수 있었다.

 

 

 

 

---

 

 

이때 돌아가며 하나하나 빼주는 방식보다 list 형식으로 나열하여 Concat으로 한번에 넣어주는 방식이 성능상으로 유리하기 때문에 Stack을 사용하여 나열 + 이전 숫자 확인을 할 수 있는 구조로 만들었다.

 

 

public string solution(string number, int k)
{
    Stack<char> stack = new Stack<char>();

    foreach (char c in number)
    {
        while (stack.Count > 0 && k > 0 && stack.Peek() < c)
        {
            stack.Pop();
            k--;
        }
        stack.Push(c);
    }
    while (k > 0)
    {
        stack.Pop();
        k--;
    }

    var result = stack.Reverse(); // Stack은 뒤집기
    return string.Concat(result); // << 문자열을 하나하나 더하기 보다 Concat을 사용하는것이 성능상 유리
}