[BOJ] 2812.크게 만들기(Stack).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제가 짧아서 금방 풀 수 있을 줄만 알았지만..

생각보다 오랜 시간 고민을 했던 것 같다. T_T

기본적인 동작은 stack에 각 자리의 숫자를 추가해주는데,

추가해주기 전에 stack의 top과 비교를 하고 현재 자릿수가 더 크다면 top에 있는 숫자를 지워주자.

이 동작은 지울 수 있는 숫자의 개수가 남아있다면 계속 반복할 수 있다.

위 동작을 마친 후 현재 자릿수를 stack에 추가해주자.

//

deque로 해결한 사람들도 있고 list를 사용하여 해결한 사람도 있고

다양한 해결방법이 있는 것 같다.

그래도 현재 만들어진 숫자의 끝자리를 확인하고(peek()), 삭제해주는(pop()) 동작이

stack 자료구조에 더 가까운 것 같다.

#. Code

stack에 있는 요소들을 System.out.println() 으로 출력해주다 보니 속도가 상당히 느리게 나왔다.

범위가 (1 ≤ K < N ≤ 500,000) 라서 최악의 경우 499,999번 System.out.println() 을 호출하게 되는데

System.out.println() 는 비싼(?) 메서드라서 속도가 1864ms 나왔었다.

StringBuffer 를 사용하면 380ms 까지 속도를 올릴 수 있다!_!

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 46 47 48 49 50 51

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer;   public class BOJ2812 {       static int N, K;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           N = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());           String num = br.readLine();         Stack<Integer> res = process(num);                  StringBuffer sb = new StringBuffer();         for (int i = 0; i < N - K; i++) {             sb.append(res.get(i));         }         System.out.println(sb);     }       private static Stack<Integer> process(String num) {           int cnt = 0; // 지운 숫자의 개수         Stack<Integer> stack = new Stack<>();           for (int i = 0; i < N; i++) {             // 현재 숫자             int now = num.charAt(i) - '0';             // 아직 숫자를 더 지울 수 있고, stack의 top보다 지금 숫자보다 더 크다면              while (cnt < K && !stack.isEmpty() && stack.peek() < now) {                 // top에 있는 숫자를 지워주자.                 stack.pop();                 cnt++;             }             // 새로운 숫자를 추가             stack.add(now);         }           return stack;     }   }   Colored by Color Scripter

cs