프로그래머스 - 큰 수 만들기

문제 링크

첫 제출(실패)

using System;

public class Solution {
    public string solution(string number, int k)
    {
        var sb = new System.Text.StringBuilder(number);
        for (var i = 0; i < sb.Length - 1 && k > 0; i++)
        {
            if (i < 0) i = 0;
            var current = sb[i];
            var next = sb[i + 1];

            if (current >= next) continue;
            sb.Remove(i, 1);
            i -= 2;
            k--;
        }

        if (k > 0)
        {
            sb.Length -= k;
        }      
        return sb.ToString();
    }
}

돌이켜보면 왜 이렇게 작성했는지 모르겠다. sb.Remove()는 내부 요소 재정렬로 인해 O(N)의 시간 복잡도를 갖는다. 직접 중간요소를 빼는 것보다, 새로운 공간에 앞에서부터 쌓아나가는 방식이 훨씬 더 낫다.

두 번째 제출(성공)

using System;

public class Solution {
    public string solution(string number, int k)
    {
        var answer = new char[number.Length];
        var nextIndex = 0;
        var leftCount = k;
        foreach (var current in number)
        {
            while (nextIndex > 0 && leftCount > 0 && answer[nextIndex - 1] < current)
            {
                nextIndex--;
                leftCount--;
            }
            
            answer[nextIndex++] = current;
        }

        return new string(answer, 0, number.Length - k);
    }
}

스택의 개념을 사용했다. 아직 제거할 수 있는 개수가 있고 다음에 온 숫자가 앞선 숫자보다 크다면 기존 숫자를 제거한다. 만약 이미 주어진 개수만큼 제거했다면 남은 건 그대로 이어붙이고, 끝까지 갔는데 제거해야 할 개수가 남았다면(내림차순 위주의 입력인 경우 이런 상황이 만들어질 수 있다.) 그냥 뒤에서부터 남은 개수를 잘라낸다.