[C#]큰 수 만들기 (탐욕법)

프로그래머스 문제

문제 설명

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

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

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

제한 조건

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

입출력 예

number                                                          k                                                                 return

1924	2	94
1231234	3	3234
4177252841	4	775841

 

내 풀이

using System;
using System.Collections.Generic;

public class Solution {
    public string solution(string number, int k) {
        int numSize = number.Length - k;
        List<int> temp = new List<int>(numSize);
        int start = 0;
        for(int i=0; i<numSize; i++) 
        {
        char maxNum = number[start];
        int maxIdx = start;
        for(int j=start; j<=k+i; j++) 
        {
            if(maxNum < number[j]) 
            {
                maxNum = number[j];
                maxIdx = j;
            }
        }
            start = maxIdx + 1;
            temp.Add((int)Char.GetNumericValue(maxNum));
        }
        string answer = string.Join("",temp);
        return answer;
    }
}

느낀점: 많은 시행착오가 있었다. 반목문을 진행시킬 정확한 조건을 찾는 것 부터 어려웠으며

 

처음에는 반복문을 함수로 돌려서 조건에 부합할때 까지 돌려주려하다가 이중 반목문 안에 빈 String 변수를 두고 채워나간 후

 

리턴하면 되겠다 싶어 그 방식으로 진행하였다. 하지만 테스트 케이스 9번,10번에서 런타임 오류가 발생하였고

 

나는 조금이라도 수행 시간을 줄여주기 위해 List를 두고 이중 반복문 을 돌려 조건에 부합할때 그 수를 바로 List에 Add해주었다.

 

그렇게 진행하니 모든 테스트케이스를 만족시킬 수 있었다.