[알고리즘] 프로그래머스 - 큰 수 만들기 c++

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42883

틀린이유

• 가장 큰 수 만들려면 가장 작은 수 k개 제거하면 된다고 생각함
• 가장 큰 패 원인은 입출력 예시를 제대로 보지 않음 (세 번째 예시가 나의 생각에 대한 반례였음..)
  → 1, 2 예시라는 부분을 보고 내 생각 전체가 맞다고 판단했기 때문에 판단 오류를 범함
• 큰 수를 만들기 위해서는 앞쪽에 큰 수들을 남겨놓아야한다는 생각 자체를 못함

문제 분석

문제

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

입력

• number string으로 입력 받음
• 2 ≤ number.size() ≤ 10^6
• 1 ≤ k < number.size()

구현 방법

가장 큰 수를 만든다 -> 앞자리가 큰 숫자가 오는 것이 큰 수

앞자리에 큰 것만 남기기 위해서는 어떤 자료구조를 사용할 수 있을까?
➡️ 스택

스택의 top과 들어오는 수를 비교해서

• 들어오는 수가 더 크다면 스택 top이 더 크거나 같을때까지 pop
• 들어오는 수가 더 작으면 push

+) k개 제거할 수 있으므로

• pop 할 때 k가 현재 0보다 큰 지 check 해줘야 함
• number 끝까지 돈 후 k가 0보다 크다면 아직 제거 다 안한 것이므로 뒤에서 k개 제거해줘야 함

전체 코드

#include <bits/stdc++.h>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> S;
    S.push(number[0]);
    for (int i=1; i<number.size(); i++){
        while (k >0 && !S.empty() && number[i] > S.top()){
            S.pop(); k--;
        }
        S.push(number[i]);
    }
    if (k-- > 0 && !S.empty()) S.pop();
    while (!S.empty()){
        char c = S.top(); S.pop();
        answer = c + answer;
    }
    return answer;
}

결과

📌 배울점

큰 수 만들기, 앞자리에 큰 수만 남겨놓아야할 때는 스택을 꼭 꼭 생각하자!

+) 그래도 number의 크기(10^6)을 보고 이중 for문과 완전 탐색은 시간복잡도 1초 이내로 불가능하다는 것을 계산한 것은 아주 잘했다!👏

구현, 스택, 그리디 열심히 풀어야겠다. 유형별로 풀어보니까 보완할 유형이 보이기 시작했다. 그리고 무엇보다 가장 중요한 거! 미리 판단하지 말자. 이거 완전 내가 가지고 있는 클루지다!!!