프로그래머스 큰수만들기

• 큰 수 만들기

• darklight

  sublimevimemacs

  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의 자릿수 미만인 자연수입니다.

입출력 예

numberkreturn

1924	2	94
1231234	3	3234
4177252841	4	775841

 

풀이 ) 맨처음에는 정렬 하면 되지않나 싶었는데 

예제 3 .을 보면 글자의 순서는 바뀌지 않다는것 1429 엿다고 94가 최고숫자가 아님 429 이면 49가 제일 큰숫자라는게 있었다.

그래서 while 문 조건(범위,중복)만 잘맞춰주면 완성되는 문제 인거같다고 생각하게 되었다.

 

 

 

 

 
int main()
{
    string number = "4177252841";
    int k = 4;
    
    //글자의 순서는 바뀌지 않음
    //1429 엿다고 94가 최고숫자가 아님
    //1429 이면 49가 제일 큰숫자
 
    int Itemp =0;
    
    
    
    int Nsize = number.size() - k;
    int index = 0;
    string answer = "";
    int cylcle = 0;
    while (answer.size() !=Nsize)
    {
        index = 0;
        Itemp = 0;
        if (cylcle == 0)
        {
            for (int i = 0; i < number.size() - Nsize + 1; i++) //k개의 숫자를 잘라서 만드는게 길이이고 0부터 시작하므로 +1까지
            {
                if (Itemp == 0)  //처음이면 0이니까 넣어준다
                {
                    Itemp = number.at(i) - '0';
                    index = i;
                    cout << Itemp << endl;
                }
                else if (Itemp >= number.at(i) - '0') // 더크거나 같으면 앞에꺼를 넣어주고
                {
                    continue;
                }
                else
                {
                    Itemp = number.at(i) - '0';  //i번쨰가 크다면 i숫자를 기억하고 위치기억
                    index = i;
 
                }
            }
        }
 
        
        else
        {
            for (int i = 0+cylcle; i < number.size() +answer.size() -Nsize+1; i++) //돌면서 기억한 위치뒤를확인하는데 범위가 넘어가지않게
            {
                cout << number.at(i) << " ";
                if (Itemp == 0)
                {
                    Itemp = number.at(i) - '0';
                    index = i;
                    cout << Itemp << endl;
                }
                else if (Itemp >= number.at(i) - '0')
                {
                    continue;
                }
                else
                {
                    Itemp = number.at(i) - '0';
                    index = i;
 
                }
            }
        }
        answer += number.at(index); //위치기억한곳에 넣어주자
        
        cylcle += index+1 -cylcle; //for문을 위한 위치기억
        cout << index << "번쨰" << Itemp << endl; //테스트위함
        
    }
 
 
    cout << answer; //답
 
 
    
    
    
 
    
    
 
    
    
 
 
    return 0;
 
 
}