백준 2812 크게 만들기

작성일 | In |

Problem : 크게 만들기

유형 : 그리디

문제 해석

  • N자리 숫자에서 숫자 K개를 지워서 가장 큰 수를 만들어라.
  • 숫자가 0으로 시작하는 경우는 존재하지않고, 50만 이하이다.
    • O(NlogN) 이하의 풀이로 해결해야한다.

해결 전략

  • K개 이하를 지우는것이 아니고, K개를 반드시 지워야 하므로 간단하다.
  • 1924가 있고 2개를 지운다고 하면 직관적으로 94를 도출해낼 수 있다.
  • 이것은 2개 이하를 지울때 큰수가 앞에 존재해야 한다는 직관에서 도출되는것이다.
    • 1은 9보다 작으므로 삭제된다. {9}
    • 9는 2보다 크므로 남아있는다. {92}
    • 2는 4보다 작으므로 남아있는다 {94}

즉 지울수 있는 상황일때 맨 뒤의 숫자 보다 더 큰수가 등장하면, 만들어진 수중 맨뒤에 있는 숫자를 지워주면된다.
숫자를 완성했는데, 지워야하는 숫자가 남아있다면 뒤에서부터 지워주면된다.

예시를 들자면

45321이 있고 2개를 지운다고 하자.

지울수 있는 상황일때 맨 뒤의 숫자 보다 더 큰수가 등장하면, 만들어진 수중 맨뒤에 있는 숫자를 지워주면된다. 라는 규칙에 따라서 일단 5321이 완성된다.

  • 이중에 한개를 더 지워야하는데, 가장 큰수가 되려면 가장 작은 숫자를 지우면된다.
  • 이것은 이전처럼 맨뒤에서부터 숫자를 지우면 된다.
    • 왜냐하면 더 큰수가 등장하면 앞에 있는 숫자를 지워주면된다 라는 과정을 이미 지나왔으므로, 임시적으로 완성된 숫자는 내림차순이 되어있을것이기 때문이다.

구현

  • 지울수 있는 상황이고, 새로운 숫자가 앞의 숫자보다 크다면 앞의 숫자를 지운다.
  • 지워야되는 숫자의 개수가 남아있다면 맨뒤부터 지운다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>

using namespace std;

void solve();

bool isBigger(const string &answer, const char &num);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("input.txt", "r", stdin);

  solve();

  return 0;
}

void solve() {
  int n, k;
  cin >> n >> k;

  string number;
  cin >> number;

  string answer;
  for (char num : number) {
    while (k > 0 && !answer.empty() && isBigger(answer, num)) {
      answer.pop_back();
      k--;
    }
    answer.push_back(num);
  }

  while (k > 0) {
    answer.pop_back();
    k--;
  }

  cout << answer;
}

bool isBigger(const string &answer, const char &num) {
  return answer.back() < num;
}

참고

  • 사실 이문제는 프로그래머스 큰 수 만들기 와 동일한 문제이다.
  • 과거 풀어봤던 문제였었고, 오랜만에 만난김에 프로그래머스 저지내에서 Java로 한번 다시 구현해보았다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();

        for (char num : number.toCharArray()) {
            while (k > 0 && (answer.length() > 0) && isBigger(answer, num)) {
                answer.deleteCharAt(answer.length() - 1);
                k--;
            }
            answer.append(num);
        }

        while (k > 0) {
            answer.deleteCharAt(answer.length() - 1);
            k--;
        }
        return answer.toString();
    }

    private boolean isBigger(final StringBuilder answer, final char num) {
        return answer.charAt(answer.length() - 1) < num;
    }
}
  • 자바의 경우 문자열 그대로 다루기가 조금 불편한것 같다.
  • 차라리 스택으로 구현하는게 더 편했을법하다.