[ 백준 ] 2812 / 크게 만들기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
96/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2812 / 크게 만들기
 *
 * Kind :: Greedy + Math
 *
 * Insight
 * - N 자리 숫자에서 K 개를 지워야 하므로
 *   남는 숫자는 (N-K) 자리 숫자이다
 *   + 예제 입력 1
 *     4 2
 *     1924
 *     # 9 앞의 1 을 없애고
 *       4 앞의 2 를 없애야
 *       94 로 가장 큰 수를 만들 수 있다
 *   + 예제 입력 변형 1
 *     5 2
 *     12924
 *     # 9 앞의 1,2 를 없애야
 *       924 로 가장 큰 수를 만들 수 있다
 *   + 예제 입력 변형 2
 *     5 3
 *     12924
 *     # 9 앞의 1,2 를 없애고
 *       4 앞의 2 를 없애야
 *       94 로 가장 큰 수를 만들 수 있다
 *   + 예제 입력 변형 3
 *     5 1
 *     12924
 *     # 9 앞의 1 을 없애야
 *       2924 로 가장 큰 수를 만들 수 있다
 *
 * - 주어진 숫자의 맨 앞자리 숫자부터 하나씩 차례로 볼 때
 *   현재 숫자가 이전 숫자보다 크면
 *   이전의 숫자들을 최대한 지워준다!
 *   + 하긴... 이렇게 해야지 맨 앞자리에 최대한 가장 큰 숫자가 올 수 있기에
 *     최종적으로 가장 큰 수를 만들 수 있다
 *     # 예제 입력 변형 4
 *       5 3
 *       15243
 *       -> 1
 *          15 => 5 (K = 3->2)
 *          52
 *          524 => 54 (K = 2->1)
 *          543 / 지우기 끝
 *          54 (K = 1->0)
 *          => 위에서 말한대로 현재 숫자가 이전 숫자보다 크다면
 *             이전 숫자들 중에서 현재 숫자보다 작은 모든 숫자들을 최대한 지워준다
 *             이때, 어떤 경우에는 위처럼 지워주고도 마지막에 K 가 남는 경우가 있는데
 *             이 경우 만든 큰 수에서 맨 뒷자리를 하나씩 없앰으로써 자리수를 맞춰준다
 *             (K 가 남을 때 만들어진 큰 수는 내림차순으로 정렬될 수 밖이 없기 때문!)
 *
 * Point
 * - 현재 만들어진 가장 큰 수의 맨 뒷자리 숫자를 지우거나, 맨 뒷자리에 숫자를 추가해야한다
 *   # 위와 같은 연산을 하는 데 있어 가장 좋은 자료구조는 스택이다!
 *     + 스택을 이용해서 가장 큰 수를 만들어주자
 *       -> C++ 의 string 은 push_back, pop_back 메소드가 있어
 *          스택으로 활용가능하다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, K;
    cin >> N >> K;
    string D; cin >> D;

    // Process
    string A; /* 만들 수 있는 가장 큰 수 */
    A.push_back(D[0]); /* 초기화 */
    int len = D.length();
    int i = 1;
    while (i < len) {
        /* K 가 남아있고 A 가 비어있지 않는 한
         * 현재 숫자(D[i])가 현재 만들어진 가장 큰 수의 맨 뒷자리 숫자(A.back()) 보다 크다면 */
        while (K > 0 && not(A.empty()) && D[i] > A.back()) {
            A.pop_back(); /* 현재 만들어진 가장 큰 수의 맨 뒷자리가
                           * 현재 숫자보다 작지 않을 때까지 최대한 지워줌 */
            K--; /* K 감소 */
        }
        A.push_back(D[i]); /* 현재 숫자를 현재 만들어진 가장 큰 수 맨 뒷자리에 추가 */
        i++; /* 인덱스 갱신 */
    }

    while (K--) { /* K 가 남아있다면 */
        /* 현재 만들어진 가장 큰 수는 내림차순으로 정렬된 상태 */
        A.pop_back(); /* 현재 만들어진 가장 큰 수의 맨 뒷자리부터 K 자리만큼 제거 */
    }

    // Control : Output
    cout << A << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글