107. 큰 수 만들기

 

기본 틀 :

 

using System;

public class Solution {
    public string solution(string number, int k) {
        string answer = "";
        return answer;
    }
}

 

문제가 쉬워보였지만 상당히 애먹었다...

 

처음에는 number.Legnth - k 개 문자열을 구성한 후 

 

해당 문자열에서 가장 작은 수를 제거하고

 

number에 남은 앞 글자를 추가하는 방식으로

 

max 값을 찾고자 했다...

 

그런데 그럴 경우 "시간 초과" 발생했다...

 

도무지 다른 방법이 보이지 않아서 다른 사람의 코드를 찾아보니

 

StringBuilder와 탐욕 기법으로 문제를 하셨다.

 

using System.Text;

 

        StringBuilder sb = new StringBuilder();

 

using System.Text; 로 import 할 수 있었고

 

StringBuilder sb = new StringBuilder()로 선언 가능했다.

 

탐욕 기법은

	// 탐욕 기법
        // 문자열 앞에서 부터 큰 수를 찾고 뒤의 큰 수를 찾는 과정 반복
        for(int i = 0, index = -1; i < number.Length - k; i++)
        {
            char max = '0';
            
            for(int j = index + 1; j <= k + i; j++)
            {
                // 유니코드 비교
                // '0' : 48 ~ '9' : 57
                // 이라 비교문 동작 가능
                if(max < number[j])
                {
                    max = number[j];
                    // index를 조정해 이전에 찾은 최대값 다시 찾지 않도록 설정
                    index = j;
                }
            }
            
            // '+' 연산자와 동일하지만 
            // '+' 연산자는 글자 추가마다 새로운 문자열로 만드는 형식인데
            // append는 그냥 붙이는 형식이라 성능이 더 우수하다
            sb.Append(max);
        }

 

for문을 사용해 number를 순회하는데 이때 특이한 점은 int i 뿐만 아니라, index = -1을 선언하는 것이다.

 

이 index는 하나의 가장 큰 숫자를 찾은 이후 그 뒤 문자열에서 다음 제일 큰 숫자를 찾기 위해서 사용 됐다.

 

전체 코드 : 

 

using System;
using System.Text;

public class Solution {
    public string solution(string number, int k) 
    {
        StringBuilder sb = new StringBuilder();
        
        // 탐욕 기법
        // 문자열 앞에서 부터 큰 수를 찾고 뒤의 큰 수를 찾는 과정 반복
        for(int i = 0, index = -1; i < number.Length - k; i++)
        {
            char max = '0';
            
            for(int j = index + 1; j <= k + i; j++)
            {
                // 유니코드 비교
                // '0' : 48 ~ '9' : 57
                // 이라 비교문 동작 가능
                if(max < number[j])
                {
                    max = number[j];
                    // index를 조정해 이전에 찾은 최대값 다시 찾지 않도록 설정
                    index = j;
                }
            }
            
            // '+' 연산자와 동일하지만 
            // '+' 연산자는 글자 추가마다 새로운 문자열로 만드는 형식인데
            // append는 그냥 붙이는 형식이라 성능이 더 우수하다
            sb.Append(max);
        }
        
        // 문자열로 변환 후 반환
        return sb.ToString();
    }
}