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

문제 링크

코딩테스트 연습 - 큰 수 만들기

 

 

 

풀이

첫 번째 풀이로, 완전탐색으로 풀리나 해봤지만 역시나 시간초과가 걸렸다.

그리고 두 번째 풀이로, 최댓값을 골라서 같은지 비교했으나 테스트케이스 10번에서 시간이 초과된다.

세 번째 풀이는 제거할 개수 범위 내에 가장 앞 숫자보다 큰 숫자가 있는지 검사하는 방법이다.

 

예를 들어,

현재 인덱스는 5라면, 제거할 개수가 4개라면 [5]가 [6] ~ [9]까지 비교했을 때, 가장 큰 값인지 검사하면 된다.

[6]~[9]까지 max_element로 찾았더니 테스트케이스 10번에서 시간이 초과된다.

중간에 찾으면 break; 로 시간을 줄여야 통과할 수 있다.

 

여기서, 반복문의 탈출 조건은

1. 제거할 개수가 0일 때

2. 제거할 개수와 남은 개수가 같을 때

두 가지이다.

 

// process

반복문(number.length() 까지)    --- 사실, 탈출 조건을 보면 length까지 안해도 탈출한다.)

{

    (현재 인덱스 + 제거할 개수)까지 돌면서 현재 인덱스 원소보다 큰 경우,

    제거할 개수 감소

    제거할 원소는 '#' 처리(나중에 후처리)

 

    탈출 조건 1. 제거할 개수가 0일 때

    탈출 조건 2. 제거할 개수와 남은 개수가 같을 때

}

 

처음부터 반복문 돌면서 '#'이 아닌 곳만 answer에 추가해준다(char 형으로)

 

answer 리턴;

 

#include <string>
#include <vector>

using namespace std;

// 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자

// 숫자 number
// 제거할 갯수 k

string solution(string number, int k) {
    string answer = "";
    
    // process
    for(int i=0; i<number.length(); i++){
        int end = i+k;            // 제거할 개수 범위 마지막
        for(int j=i+1; j<=end; j++){
            if(number[i] >= number[j]) continue;        // 현재 수보다 큰 숫자가 있는지 비교
            number[i] = '#';        // 제거
            k--;        // 제거할 개수 감소
            break;
        }
        if(k==0) break;         // 모두 제거했다.
        if(k < number.length()-i) continue;
        number.erase(number.begin()+i, number.end());   // 만약 제거할 개수랑 남은 개수랑 같다
        break;
    }
    for(int i=0; i<number.length(); i++){
        if(number[i]=='#') continue;
        answer += number[i];            // 제거할 부분이 아닌 경우만
    }
    
    return answer;      // 가장 큰 숫자 리턴
}