[PS] 99클럽 코테 스터디 20일차 TIL (큰 수 만들기)

문제

문제 링크

설명

숫자가 주어졌을때 k 개의 숫자를 제거 했을때 최대가 되는 수를 만들어야 한다.

시도해봤던 방법

문제를 잘못 이해해서 앞에서 부터 가장 작은 수를 순차적으로 k 개 제외시키는 방향으로 코드를 작성했었다. 예제에서 주어진 1924 나 1231234 의 경우엔 우연히 숫자의 배치가 맞아 떨어져서 통과했지만 4177252841 의 경우엔 477584 결과값이 나오면서 통과하지 못했다.

전체 수에서 최소 숫자를 빼는 방식으로 푸는 문제가 아니란 것을 느꼈다.

class Solution {
  public String solution(String number, int k) {
    String[] arr = number.split("");
    Arrays.sort(arr);

    StringBuilder sb = new StringBuilder(number);
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < sb.length(); j++) {
        if (String.valueOf(sb.charAt(j)).equals(arr[i])) {
          sb.deleteCharAt(j);
          break;
        }
      }
    }
    return sb.toString();
  }
}

풀이

• 그리디 알고리즘 : 최종 길이는 원래 길이에서 k 를 뺀 만큼(number.length() - k)이 된다. 그 길이를 len 이라고 할 때, 맨 앞에서부터 순차적으로 최대 숫자만을 len 개 이어 붙여야 한다.

class Solution {
  public String solution(String number, int k) {
    String answer = "";

    StringBuilder sb = new StringBuilder();
    ArrayDeque<Character> stack = new ArrayDeque<>();

    // 1
    for (int i = 0; i < number.length(); i++) {
      char c = number.charAt(i);
      while (!stack.isEmpty() && stack.peek() < c && k > 0) {
        stack.poll();
        k--;
      }
      stack.push(c);
    }

    // 2
    for (int i = 0; i < k; i++) {
      stack.pop();
    }

    // 3
    for (char c : stack) {
      sb.append(c);
    }

    return sb.reverse().toString();
  }
}

• 코드의 1 번 부분 : 맨 앞 숫자부터 확인한다. 현재 숫자가 스택에 있는 수 보다 크면 스택에 있던 수를 제거 하고 넣는다. 이때 스택에 들어있는 수가 여러개 있으면 k 범위 내에서 모두 지운다. 예를 들어 4177252841 에서 스택에 4, 1 까지 들어있는 상태에서 다음 숫자인 7 을 넣을때 앞 두개의 숫자를 모두 지워야 한다.

• 코드의 2 번 부분 : 이 부분은 999 와 같이 똑같은 숫자 조합으로 입력되는 경우, 스택에 9, 9, 9 모두 들어가기 때문에 k 만큼 제거 해야 하기 때문에 필요하다.
• 코드의 3 번 부분 : 스택 맨 윗부분 부터 sb 에 들어가 있으므로 원래 숫자 순서대로 뒤집어서 출력한다.

회고

그리디 알고리즘 문제를 많이 안풀어봐서 그런가 뭔가 정형화된 알고리즘을 이용해 푸는 느낌이 아니고, 문제를 보고 어떤 식으로 풀어나가야 될지에 대한 전략에 가깝다는 것을 느꼈다. 코드는 짧지만 생각해 내기가 쉽지 않다. 많은 문제를 풀어보면서 생각하는 연습을 해야 될 것 같다.