[백준_BOJ] 10828번 : 스택

백준 10828번 문제는 스택을 이용하여 각 기능을 구현해보는 문제이다.

• 시간 제한은 0.5초
• 명령의 수는 10,000개 이하

 

 

• 첫번째로 내가 시도한 방법은
  Scanner를 통한 입력과 Stack클래스를 사용하여 기능을 구현하고 split()메소드를 사용해서 각 명령을 구분했다.

import java.util.Scanner;
import java.util.Stack;
public class Baekjoon10828 {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		Stack<Integer> stack = new Stack<>();
		int N;
		int pushNum;
		String order;
		N = sc.nextInt();
		sc.nextLine();
		String[] part = {};
		
		for(int i = 0; i<N; i++) {
			order = sc.nextLine();
			part = order.split(" ");
			if(part[0].equals("push")) {
				pushNum = Integer.parseInt(part[1]);
				stack.push(pushNum);
			}
			else if(part[0].equals("pop")) {
				if(!stack.isEmpty()) {
					System.out.println(stack.pop());
				}else {
					System.out.println(-1);
				}
			}
			else if(part[0].equals("size")) {
				System.out.println(stack.size());
			}
			else if(part[0].equals("empty")) {
				if(stack.isEmpty()) {
					System.out.println(1);
				}else { System.out.println(0);
			}
			}
			else if(part[0].equals("top")) {
				if(!stack.isEmpty()) {
					System.out.println(stack.peek());
				}else {
					System.out.println(-1);
				}
			}
		}
	}
}

 

-결과

 

위의 방법으로 제출한 결과 성공은 했다. 하지만 488ms로 시간 초과가 날 뻔했다.

 

이 방법의 단점들은

1. Scanner의 느린 입력
   : 입력을 한 번에 한줄씩 처리하는데 호출마다 문자열을 파싱하는 과정이 있기 때문에 상대적으로 속도가 느리다.
     입력 데이터의 양이 많아질수록 효율은 더 떨어짐
   -> bufferedReader를 통해 속도 향상
2. Stack 클래스를 이용하여 스택 구현
   : Stack클래스는 Vector 인터페이스를 구현한다. 이는 동기화된 데이터 구조로 오버헤드가 발생할 수 있기 때문에 상황에 따라
     효율이 떨어질 수 있음 
3. split()메소드
   : split() 메소드는 정규표현식을 사용하기 때문에 효율이 떨어짐

 

위 단점들을 고려하여 좀 더 효율적인 방법으로 바꾼다면

• BufferedReader와 StringTokenizer, 배열을 통한 스택 구현이다.

1. 우선 배열을 통해 스택을 구현해보겠다.

class ArrayStack {
	private int[] stack;
	private int top;
	private int capacity;
	
	public ArrayStack(int size) {
		capacity = size;
		stack = new int[capacity];
		top = -1;
	}
	
	public void push(int value) {
		if(top == capacity -1) {
			System.out.println("스택 오버플로우. 스택 꽉 참");
		}
		stack[++top] = value;
	}
	public int pop() {
		if(top == -1) {
			return -1;
		}
		return stack[top--];
	}
	public int size() {
		return top + 1;
	}
	public int isEmpty() {
		if(top == -1) {
			return 1;
		}
		else return 0;
	}
	public int peek() {
		if(top == -1) {
			return -1;
		}
		return stack[top];
	}
}

 

2. bufferedReader를 통해 입력을 받는다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	ArrayStack stack = new ArrayStack(N);

 

      명령의 개수 N을 입력받고 N을 스택의 크기로 넘겨준다. (명령의 개수보다 커지지 않음)

3. StringTokenizer를 통해 입력 문자열을 공백(" ") 기준으로 나누고 명령을 인식한다. (N번 동안)

for(int i = 0; i<N; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	String order = st.nextToken();
			
	switch(order) {
		case "push" :
			int value = Integer.parseInt(st.nextToken());
			stack.push(value);
			break;
		case "pop" :
			System.out.println(stack.pop());
			break;
		case "size" :
			System.out.println(stack.size());
			break;
		case "empty" :
			System.out.println(stack.isEmpty());
			break;
		case "top" :
			System.out.println(stack.top());
			break;
	}
}

 

스위치문을 사용해 전의 if-else문보다 가독성을 더 높였다.

 

-전체코드

package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class ArrayStack {
	private int[] stack;
	private int top;
	private int capacity;
	
	public ArrayStack(int size) {
		capacity = size;
		stack = new int[capacity];
		top = -1;
	}
	
	public void push(int value) {
		if(top == capacity -1) {
			System.out.println("스택 오버플로우. 스택 꽉 참");
		}
		stack[++top] = value;
	}
	public int pop() {
		if(top == -1) {
			return -1;
		}
		return stack[top--];
	}
	public int size() {
		return top + 1;
	}
	public int isEmpty() {
		if(top == -1) {
			return 1;
		}
		else return 0;
	}
	public int top() {
		if(top == -1) {
			return -1;
		}
		return stack[top];
	}
}

public class Baekjoon10828 {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayStack stack = new ArrayStack(N);
		for(int i = 0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String order = st.nextToken();
			
			switch(order) {
				case "push" :
					int value = Integer.parseInt(st.nextToken());
					stack.push(value);
					break;
				case "pop" :
					System.out.println(stack.pop());
					break;
				case "size" :
					System.out.println(stack.size());
					break;
				case "empty" :
					System.out.println(stack.isEmpty());
					break;
				case "top" :
					System.out.println(stack.top());
					break;
			}
		}
	}
}

 

 

실행결과 280ms로 줄어든 것을 볼 수 있다.

 

 

 

 

 

 

 

아직 실력이 많이 부족해 지적, 수정 및 피드백 해주시면 감사하겠습니다!