[프로그래머스 C#] 큰 수 만들기

문제 

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

프로그래머스

문제 설명

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

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

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

제한 조건

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

 

풀이 

1 가장 큰 수 찾기 

0번 인덱스와 1번부터 비교 더 큰 수를 저장하기

가장 큰 수 뒤에 (길이-인덱스)>=길이 - k -1이어야 함  (인덱스로 생각하면 앞에서부터 k+i까지에서 찾기 )

 

예를 들면 4177252841 이 주어졌을 때 k=4이면 

맨 처음엔 뒤에 5개를 두고 찾아야 한다. 

4 1 7 7 2  ] (처음엔 여기까지만 반복) [ 5 2 8 4 1 

 

가장 큰 수 string 넣기 

2 제일 큰 수 인덱스 다음부터 큰 수 찾기 
- 마찬가지로 큰 수 뒤에 (길이 - 인덱스) >= 길이 -k-2이어야 함
3 반복 : 길이 -k-1부터 자릿수 바꿀 때마다 커지기 

 

코드

using System;
using System.Text;
public class Solution {
    public string solution(string number, int k) {
        string answer = "";
        StringBuilder sb = new StringBuilder();
        
        int n=number.Length-k;
        
        //자리수 만큼 반복 
        for(int i=0, idx=-1; i<n; i++) 
        {
            char max = '0'; 
            // idx 다음 인덱스부터 k+i와 작거나 같을 때 까지 반복한다. 
            for(int j=idx+1; j<=k+i; j++)
            {
                //비교해서 max값 넣어주기
                if(max<number[j])
                {
                    max = number[j];
                    idx = j;
                }
            }
            sb.Append(max); //StringBuilder에 추가한다.
        }
        
        answer = sb.ToString(); 
        
        return answer;
    }
}

StringBuilder 가 string+stirng 보다 효율이 좋다고 한다.