# 10828 - 스택 (Stack)

1. 문제

 

10828번: 스택

명령이 주어지면 stack에 메소드인 push, pop, size, empty, top 을 구현하고, 해당 결과를 출력하면 된다.

---

2. 제출 결과

---

3. 문제 발생 > 시간 초과

stack 기능에 맞게 구현 동작은 잘 작성한 것 같은데 시간 초과가 발생했다.

생각을 해보니, 이 문제에는 시간 제한이 존재하여 0.5초 안에 출력이 다 되어야 한다.

기존에 작성한 코드는 println()으로 switch 문 안에서 해당 rule (push, pop, size ..) 등등 조건에 맞는 케이스에 원하는 값을 출력할 수 있도록 작성했었다.

가뜩이나 println()은 한 줄에 하나를 출력하는 것만해도 오래 걸리는데..

조건에 맞는 케이스에 해당할 때마다 한 문장씩 출력하다보니 시간 초과가 발생한 것 같다.

• 기존 코드

switch (rule) {
                case "push": {
                    stack.push(num);
                    break;
                }
                case "pop": {
                    if (stack.isEmpty()) {
                        System.out.println(-1);
                        break;
                    } else {
                        System.out.println(stack.peek());
                        stack.pop();
                        break;
                    }
                }
                case "size": {
                    System.out.println(stack.size());
                    break;
                }
                case "empty": {
                    if (stack.isEmpty()) {
                        System.out.println(1);
                        break;
                    } else {
                        System.out.println(0);
                        break;
                    }
                }
                case "top": {
                    if (stack.isEmpty()) {
                        System.out.println(-1);
                        break;
                    } else {
                        System.out.println(stack.peek());
                        break;
                    }
                }
            }

---

4. 시간 초과 해결 방법

N 개의 줄에 명령이 하나씩 주어지게 되는데, 명령의 수 범위가 1 <= n <= 10,000이다.

따라서, 해당 명령에 대한 결과를 println()으로 한 줄씩 출력하는 것보다 StringBuilder 를 사용해서

출력할 문장을 하나로 만들고 한 번에 출력했더니 시간 초과를 해결할 수 있었다!

 

• StringBuilder 를 사용한 코드

public static StringBuilder solution(String[] arr) {
		Stack<Integer> stack = new Stack<>();
		StringBuilder sb = new StringBuilder(); // StringBuilder 선언

		String rule = "";
		int num = 0;
		for (String s : arr) {
			if (s.contains(" ")) { 
				rule = s.substring(0, 4);
				num = Integer.parseInt(s.substring(5, s.length()));
			} else {
				rule = s;
			}

			switch (rule) {
			case "push": {
				stack.push(num);
				break;
			}
			case "pop": {
				if (stack.isEmpty()) {
					sb.append(-1).append("\n");
					break;
				} else {
					sb.append(stack.peek()).append("\n");
					stack.pop();
					break;
				}
			}
			case "size": {
				sb.append(stack.size()).append("\n");
				break;
			}
			case "empty": {
				if (stack.isEmpty()) {
					sb.append(1).append("\n");
					break;
				} else {
					sb.append(0).append("\n");
					break;
				}
			}
			case "top": {
				if (stack.isEmpty()) {
					sb.append(-1).append("\n");
					break;
				} else {
					sb.append(stack.peek()).append("\n");
					break;
				}
			}
			}
		}
		return sb;
	}

 

 

출력 값으로 스택 안에 있는 값들을 아래로 내려가는 형태로 출력을 해야 되니까 

출력 문장을 만들 때, 개행 문자도 삽입해 줬다.

그리고 void 가 아닌 리턴 타입을 StringBuilder로 하고, 실행 메서드에서 println()으로 출력했다.

 

여기서 알게 된 게 있는데.. StringBuilder 사용 시에 개행 문자 삽입할 때에도 시간 차이가 발생했다.

StringBuilder sb = new StringBuilder();
sb.append("------\n");

sb.append("------").append("\n");

처음에는 개행문자를 append 안에 같이 삽입해 줬는데, 나눠서 사용하는 게 속도가 더 빨랐다..!

 

 

거의 프로그래머스에서 문제를 풀다 보니 입출력에 대해서는 깊게 생각해 본 적이 없었다.

백준에서 문제를 풀 때 Scanner와 System.out.println을 많이 사용했었는데,

이번 스택 문제로 시간 초과를 겪으면서 앞으로 BufferedReader와 StringBuilder를 사용해 보도록 해야겠다! 

 

 

---

5. JAVA 출력 속도 비교 (참고용)

 

총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정

10 번 측정해서 평균값을 순위로 매긴 것이다.

순위	언어	출력 방법	평균 (초)
1	Java	BufferedWriter, bf.write(i + "\n");	0.9581
2	Java	StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb);	1.1881
3	Java	BufferedWriter, bf.write(Integer.toString(i)); bf.newLine();	1.2556
4	Java	PrintWriter	1.954
5	Java	System.out.println(i);	30.013

 

출력 속도 비교

 

 

---

6. JAVA 입력 속도 비교 (참고용)

 

첫째 줄에 정수의 개수 N(= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는 데 걸리는 시간을 측정.

10번 측정해서 평균값으로 순위를 매긴 것이다.

순위	언어	입력 방법	평균 (초)
1	Java	BufferedReader, Integer.parseInt	0.6585
2	Java	Scanner	4.8448

 

입력 속도 비교