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

 

 

문제

소스코드

 

#include <string>
using namespace std;
string solution(string number, int k) {
    int count = k;
    //K만큼 반복문을 돌며 내림차순으로 찾는다.
    for (int i = 0; i < k; ++i) {
 
        //현재와 다음을 비교해서 현재가 더 작은수라면 삭제
        for (int i = 0; i < number.size() - 1; ++i) {
 
            //다음값이 더 크니까 삭제
            if (number[i] < number[i + 1]) {
 
                //찾은 값삭제
                number.erase(i, 1);
                --count;
                break;
            }
        }
    }
 
    //예외 처리 테스트 케이스(12)
    if (count != 0) {
        for (int i = 0; i < count; ++i) {
            number.pop_back();
        }
        return number;
    }
    return number;
}
 

 

후기

이 문제를 해결하기 위한 키워드는 그리디이다.

 

이 문제는 그리디(탐욕) 알고리즘을 사용하는 문제로 나는 앞에 수와 다음수를 비교해서 다음 수가 더 크다면 지우는 방식으로 해서 문제를 풀었다. 이렇게 까지 풀면 테스트 케이스 12번을 제외하고는 다 통과를 할 수 있다.

 

문제는 마지막 테스트 케이스인대 

"99991" , 3 여기서 answer은 99 인대 나는 91이 나와서 계속 오류가 발생해서 22~26번 줄에 예외 처리를 해서 억지 느낌으로 통과했다. 아마 테스트 케이스가 많이 허술해서 통과할 수 있던 거 같고 다른 사람의 풀이를 보면 얼마나 멍청하게 풀었는지 알 수 있는 문제였다.

 

 

출처 및 레퍼런스

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42883