[Programmers Level2] 큰 수 만들기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

 

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

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

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

 

 

[제한 사항]

 

 

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

 

 

[입출력 예]

 

 

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

[문제 풀이]

 

완전 탐색으로 풀려했으나 입력 범위가 'number는 2자리 이상, 1,000,000자리 이하인 숫자' 여서

시간 초과가 발생하는 것이 뻔했다. 그래서 그리디로 풀려고 노력했다.

 

우선 이 문제를 풀기 위해 스택을 사용하였다.

 

내 알고리즘은

 

• 스택을 생성한다.
• for 문을 통해 number를 순회한다.
  • 스택이 비어있다면 스택에 number의 값을 넣는다.
  • 스택이 비어있지않고, 스택의 top이 number 값보다 작고, k(제거해야하는 개수)가 0이 아닐 때
    • 위 조건을 만족하지않을 때 까지 스택에서 빼고, k를 1씩 감소시킨다.
  • 스택에 number의 값을 넣는다.
• k(제거해야하는 개수)가 0이 안되는 테스트 케이스가 존재한다. (내림차순일 때 : number = "9876", k = 1, return : "987")
  
  • k를 1씩 감소시키며 k == 0이 될때까지 스택에서 뺀다.
• 스택이 빌때까지 스택에서 하나씩 꺼내며 문자열에 붙인다.
• 뒤에서 부터 붙였으므로 reverse 함수를 이용하여 거꾸로 뒤집어주고 반환한다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    stack<int> st;
    int len = number.length();
    for (int i = 0; i < len; ++i) {
        if (st.empty()) {
            st.push(number[i] - '0');
        }
        else {
            while (!st.empty() && (st.top() < number[i] - '0') && k != 0) {
                st.pop();
                k -= 1;
            }
            st.push(number[i] - '0');
        }
    }

    while (k != 0) {
        st.pop();
        k -= 1;
    }

    string answer;
    while (!st.empty()) {
        answer += to_string(st.top());
        st.pop();
    }
    reverse(answer.begin(), answer.end());
    return answer;
}