스파르타 알고리즘 트랙 문제 3일차 - 2 #10828 스택

문제

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

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

해결 과정

Stack 자료형을 활용해 주어진 입력을 구현하고 필요할 경우 출력까지 하는 코드이다.

Stack 자료형을 사용한다면 크게 어려운 문제는 아니다. 전부 해당 자료형 안에 구현되어 있기에 이를 활용하기만 하면 되었다.

 

아래는 해당 명령어를 구현하기 위해 사용한 Stack의 Method이다.

 

push x : Stack.push(x)

pop : Stack.pop()

size : Stack.size()

empty : Stack.isEmpty()

top : Stack.peek()

 

empty의 경우, Stack.Empty()도 동일한 결과를 리턴하지만, Stack.isEmpty()가 최근에 나온 Method이고 Stack.Empty()는 이전 버전과의 호환을 위해 남겨둔 Method이기에 Stack.isEmpty()를 사용하였을 뿐, Stack.Empty()를 사용해도 큰 문제는 없었다.

import java.util.Scanner; import java.util.Stack; import static java.lang.Integer.parseInt; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         int N = parseInt(a.nextLine());         Stack<Integer> arr = new Stack<>();         while (N!=0){             String[] order = a.nextLine().split(" ");             if (order[0].equals("push")){                 arr.push(parseInt(order[1]));             }             else if(order[0].equals("pop")){                 if(arr.isEmpty()) System.out.println(-1);                 else System.out.println(arr.pop());             }             else if(order[0].equals("size")){                 System.out.println(arr.size());             }             else if(order[0].equals("empty")){                 if(arr.isEmpty()) System.out.println(1);                 else System.out.println(0);             }             else if(order[0].equals("top")) {                 if(arr.isEmpty()) System.out.println(-1);                 else System.out.println(arr.peek());             }             N--;         }     } }

위에서 설명한 대로 코드를 작성하였다. 다만 값이 없을 때 -1을 출력해야 하는 부분만 가정문으로 설정해 두었다.

 

그렇지만 실행 결과는 시간 초과였다. 시간 복잡도는 O(1)이기에 이것보다 빠르게 실행할 수 없다고 생각하였음에도 시간 초과가 발생하여 팀원들에게 질문을 해 보았고, 재미있는 사실을 알게 되었다.

 

입력값을 받아올 때, 위 함수에서는 Scanner 클래스를 사용하였는데, Scanner 클래스는 입력을 받는데에 시간이 오래 걸린다. Scanner보다 빠르게 입력을 받을 수 있는 BufferedReader 라는 클래스가 있고, 이를 활용하는 것이 시간이 덜 걸린다.

 

따라서 위 코드의 Scanner 클래스를 BufferedReader 클래스로 대체해 다시 실행해 보았다.

import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class Main {     public static void main(String[] args) throws IOException {         BufferedReader a = new BufferedReader(new InputStreamReader(System.in));         int N = parseInt(a.readLine());         Stack<Integer> arr = new Stack<>();         while (N!=0){             String[] order = a.readLine().split(" ");             if (order[0].equals("push")){                 arr.push(parseInt(order[1]));             }             else if(order[0].equals("pop")){                 if(arr.isEmpty()) System.out.println(-1);                 else System.out.println(arr.pop());             }             else if(order[0].equals("size")){                 System.out.println(arr.size());             }             else if(order[0].equals("empty")){                 if(arr.isEmpty()) System.out.println(1);                 else System.out.println(0);             }             else if(order[0].equals("top")) {                 if(arr.isEmpty()) System.out.println(-1);                 else System.out.println(arr.peek());             }             N--;         }     } }

Scanner 클래스를 BufferedReader 클래스로 변경해 주었고, 이 클래스를 사용하기 위해서는 IOException 예외 선언이 필요하여 main 함수 뒤에 해당 예외를 선언해 주었다.

 

이전에 구현했던 알고리즘의 변경 없이 입력을 받아주는 클래스만 변경했음에도 시간 초과 없이 정상적으로 정답임을 확인할 수 있었다.