백준 28278: 스택2 -Java

실버4

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

문제

 

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

1. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2. 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3. 3: 스택에 들어있는 정수의 개수를 출력한다.
4. 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

 

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

 

예제 입력1

9
4
1 3
1 5
3
2
5
2
2
5

 

예제 출력1

1
2
5
3
3
-1
-1

 

자바 코드

package practice;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 명령 횟수
        int n = Integer.parseInt(br.readLine());
        
        //스택을 직접 구현 (스택 사이즈가 정해져있지 않으므로 그냥 명령어 갯수 크기로 선언)
        int[] stack = new int[n];   
        
        int top = -1; // 스택 가장 상위 값의 위치
        
        for (int i=0; i<n; i++) {
            StringBuilder cmd = new StringBuilder(br.readLine());
            StringBuilder result = new StringBuilder();
            
            // 1번 명령 
            if (cmd.length()>=3) {
                // push : 스택 위에 값을 추가
                StringTokenizer st = new StringTokenizer(cmd.toString());
                st.nextToken(); // 명령어를 의미하는 첫번째 수 pass
                
                // 스택에 넣을 정수
                int num = Integer.parseInt(st.nextToken());
                
                // 스택에 추가
                top++;
                stack[top] = num;
            } else {
                switch (cmd.toString()) {
                
                case "2":
                    // pop: 스택 가장 상위에 값을 꺼냄
                    if (top > -1) {
                        result.append(stack[top]);
                        bw.write(result.toString()+"\n");
                        stack[top] = 0;
                        top--;
                    } else {
                        result.append(-1);
                        bw.write(result.toString()+"\n");
                    }
                    
                    break;

                case "3":
                    // 현재 스택 사이즈 조회 
                    result.append(top + 1);
                    bw.write(result.toString()+"\n");

                    break;
                    
                case "4":
                    // 스택 비어있는지 확인
                    result.append(top >= 0 ? 0 : 1);
                    bw.write(result.toString()+"\n");

                    break;
                    
                case "5":
                    //peek : top 값 조회
                    result.append(top >= 0 ? stack[top] : -1);
                    bw.write(result.toString()+"\n");
                    
                    break;
                }                
            }
        }
        bw.flush();
        bw.close();            
    }
}

 

 

PS

자바에 내장된 Util 패키지에 Stack<> 클래스가 있지만, 문제에서 "스택을 구현" 한 다음이라고 한 만큼 직접 배열로 만들어보았다. 구현 자체는 바로 했는데, 시간 초과에 많은 고통을 받았다. 처음에야 출력에서 오랜 시간이 걸린다는 걸 깨닫고 System.out.pruntln을 BufferedWriter를 활용한 write() 와 flush()로 바꿨다. 하지만 시간초과는 여전했고 혹시 BufferedWriter를 쓰면서 int를 출력할 수 가 없어, String으로 변환하여 출력했던 것 때문인가 싶어서 그 다음은 String을 StringBuilder로 전부 바꿨다. 하지만 다시 시간초과가 걸렸고 혹시 배열을 써서 문제인가 싶어, 배열로 스택을 구현하는 걸 포기하고 그냥 Stack<> 클래스를 사용해서 모든 명령어들(push, pop, peek, size..)을 구현했지만 역시 여전했다. 그 쯔음부터 고통을 받기 시작했는데, 해결방법은 간단하고 황당했다. 명령어를 입력할 때 마다 출력할 수 있도록, 바로바로 flush()를 사용한 것이 시간을 잡아먹었던 것이다.. 

 

"출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다."

 

분명 출력 조건에 위와 같이 명령이 주어질 때마다 명령의 결과를 바로바로 나타내기 위해 그런 것이었는데, 그냥 버퍼에 결과들을 한줄 한줄 모아놨다가 모든 명령어가 끝난 후 한번에 flush를 하니 시간초과가 해결됐다. Stack<> 을 사용해도, 배열로 스택을 직접 구현해도 flush만 마지막 한번에 하면 해결된다. 살짝 억울하긴 했지만 그 과정에서 여러가지 시도를 해보았기에 좋은 경험으로 남으리라. 마지막으로 Stack<>을 사용한 코드를 첨부한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 명령 횟수
        int n = Integer.parseInt(br.readLine());
        
        //스택 선언(배열로 직접 구현하려했으나 시간초과가 계속 나서 .. )
        Stack<Integer> stack = new Stack<Integer>();
        
        for (int i=0; i<n; i++) {
            StringBuilder cmd = new StringBuilder(br.readLine());
            StringBuilder result = new StringBuilder();
            int num = 0;
            // 스택에 넣을 정수
            
            if (cmd.toString().length() >= 3) {
                StringTokenizer st = new StringTokenizer(cmd.toString());
                
                cmd.setLength(0); //init
                cmd.append(st.nextToken()); 
                num = Integer.parseInt(st.nextToken());
            }
            
            switch (cmd.toString()) {
            case "1":
                stack.push(num);
                break;
                    
            case "2":
                // pop: 스택 가장 상위에 값을 꺼냄
                try {
                    result.append(stack.pop());
                    bw.write(result.toString()+"\n");
                } catch (Exception e) {
                    result.append(-1);
                    bw.write(result.toString()+"\n");
                }
                break;

            case "3":
                // 현재 스택 사이즈 조회 
                result.append(stack.size());
                bw.write(result.toString()+"\n");

                break;
                    
            case "4":
                // 스택 비어있는지 확인
                result.append(stack.size() > 0 ? 0 : 1);
                bw.write(result.toString()+"\n");

                break;
                    
            case "5":
                //peek : top 값 조회
                result.append(stack.size() > 0 ? stack.peek(): -1);
                bw.write(result.toString()+"\n");
                    
                break;
            }                
        }
        bw.flush();
        bw.close();            
    }
}