[Java] 백준 2812 크게 만들기 - 골드3

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int digit = Integer.parseInt(st.nextToken());
    int canErase = Integer.parseInt(st.nextToken());
    String value = br.readLine();

    Deque<Integer> deque = new ArrayDeque<>();
    for (int i=0; i<digit; i++) {
      int val = Integer.parseInt(String.valueOf(value.charAt(i)));
      if (canErase ==0) {
        deque.addLast(val);
        continue;
      }

      if (deque.size() == 0) {
        deque.add(val);
        continue;
      }

      while (deque.size() > 0 && deque.getLast() < val && canErase != 0) {
        deque.removeLast();
        canErase--;
      }

      deque.addLast(val);
    }

    while (canErase != 0) {
      deque.pollLast();
      canErase--;
    }

    StringBuilder sb = new StringBuilder();
    for (Integer element : deque)
      sb.append(element.toString()).append("");

    System.out.println(sb.toString().trim());
  }
}

• string에서 하나씩 떼서 그 값을 deque 안에 값과 비교할 것이다
  • 만약 지울 수 있는 횟수를 초과했으면 그냥 deque 안에 더한다
  • deque안에 값이 없으면 그냥 추가한다
  • 만약 deque 맨 뒷 값이 현재 값보다 작으면 해당값을 poll해서 없애고 canErase를 하나 줄인다
• 지우는 횟수를 모두 사용하지 못했는데 string에서 모두 뗀 상태라면 남은 지우는 횟수만큼 poll해서 없애버린다
• StringBuilder로 deque 에 있는 요소들을 string으로 만들어준다

 

 

 

많이 틀린 이유

여기서 StringBuilder를 사용하지 않고 string에 += 하는 방식을 사용하면 메모리초과가 난다.

계속 새로운 리터럴이 만들어지기 때문이다. ㅜㅜ

이걸 모르고 계속 더하는 방법을 사용해서 꽤 많이 틀렸다. 이전에는 이 방법을 써도 메모리초과가 나지 않아서 심각성을 몰랐던 것 같다. 

앞으로는 StringBuilder를 자주 사용해야지.

 

 

 

 

실버1 찍었다 ㅎ