[백준] 10828번 : 스택 - JAVA [자바]

www.acmicpc.net/problem/10828

10828번: 스택

 

---

• 문제

 

 

 

 

 

 

스택 자료구조를 알고있다면 매우 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

스택 카테고리의 첫 문제는 말 그대로 스택을 이해하느냐에 초점을 두고 있다.

 

일단, 스택에 대해 모른다면 아래 글을 반드시 읽고 오시길 바란다.

 

st-lab.tistory.com/174

자바 [JAVA] - Stack (스택) 구현하기

 

 

 

우리가 크게 구현해야할 메소드는 push, pop, size, empty, top으로 크게 5가지다. 이 마저도 아주 간단한 형태라 쉽게 구현할 수 있다.

 

우리가 준비해야 할 것은 배열과 요소의 개수(size) 변수가 필요하다. 가끔 size를 배열의 크기로 알고있는 분들이 있는데, 배열의 크기가 아니라 '요소(데이터)의 개수'임을 명심하자.

 

 

 

즉, 다음과 같이 코드를 짤 수 있다.

int[] stack = new int[N];
int size = 0;
 
void push(int item) {
	stack[size] = item;	// size칸에 item을 넣고 size를 1증가 
	size++;
}
 
int pop() {
	// 데이터가 한 개도 없을 경우 -1
	if(size == 0) {
		return -1;
	}
 
	// 인덱스는 0부터 시작하므로 최상단에 있는 요소는 항상 size-1 index에 위치한다.
	else {
		int res = stack[size - 1];
		stack[size - 1] = 0;	// 0으로 초기화 해준다.
		size--;
		return res;
	}
}
 
int size() {
	return size;	// 요소 개수를 반환
}
 
int empty() {
	// 스택이 비어있으면 1 반환
	if(size == 0) {
		return 1;
	}
	else {
		return 0;
	}
}
 
int top() {
	// 데이터가 한 개도 없을 경우 -1
	if(size == 0) {
		return -1;
	}
 
	// 인덱스는 0부터 시작하므로 최상단에 있는 요소는 항상 size-1 index에 위치한다.
	else {
		return stack[size - 1];
	}
}

 

 

이를 토대로 소스만 만들어주면 된다. (사실 위 참고 링크를 보고 오셨다면 아마 금방 풀으셨을 것이다.)

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

3가지 입출력 방법을 통해 성능을 비교해보려했으나 Scanner와 System.out.println()으로 매 번 출력하면 시간초과가 뜬다. 제한 시간이 0.5초 (500ms)이기 때문에 그렇다.

 

만약 Scanner를 쓰고싶다면 StringBuilder나 BufferedWriter을 쓰면 되는데, BufferedWriter을 쓸거면 이왕 BufferedReader을 쓰는게... 여튼 아래 두 방식으로 풀어나갈 것이다. 

 

1 . Scanner + StringBuilder

2. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + StringBuilder]

 

import java.util.Scanner;
public class Main {
 
	public static int[] stack;
	public static int size = 0;
 
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int N = in.nextInt();
 
		stack = new int[N];
		
		for(int i = 0; i < N; i++) {
        
			String str = in.next();
 
			switch (str) {
            
			case "push":
				push(in.nextInt());
				break;
                
			case "pop":
				sb.append(pop()).append('\n');
				break;
                
			case "size":
				sb.append(size()).append('\n');
				break;
                
			case "empty":
				sb.append(empty()).append('\n');
				break;
                
			case "top":
				sb.append(top()).append('\n');
				break;
			}
 
		}
		System.out.println(sb);
	}
 
	public static void push(int item) {
		stack[size] = item;
		size++;
	}
    
	public static int pop() {
		if(size == 0) {
			return -1;
		}
		else {
			int res = stack[size - 1];
			stack[size - 1] = 0;
			size--;
			return res;
		}
	}
    
	public static int size() {
		return size;
	}
    
	public static int empty() {
		if(size == 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
    
	public static int top() {
		if(size == 0) {
			return -1;
		}
		else {
			return stack[size - 1];
		}
	}
	
}
 

 

 

가장 기본적인 방법이라 할 수 있겠다. 그리 어렵지 않았을 것이다.

 

 

 

 

---

- 방법 2 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 push의 경우 단어를 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static int[] stack;
	public static int size = 0;
 
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
 
		stack = new int[N];
		
		while (N-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
 
			switch (st.nextToken()) {
			
			case "push":
				push(Integer.parseInt(st.nextToken()));
				break;
				
			case "pop":
				sb.append(pop()).append('\n');
				break;
				
			case "size":
				sb.append(size()).append('\n');
				break;
				
			case "empty":
				sb.append(empty()).append('\n');
				break;
				
			case "top":
				sb.append(top()).append('\n');
				break;
			}
 
		}
		System.out.println(sb);
	}
 
	public static void push(int item) {
		stack[size] = item;
		size++;
	}
	
	public static int pop() {
		if(size == 0) {
			return -1;
		}
		else {
			int res = stack[size - 1];
			stack[size - 1] = 0;
			size--;
			return res;
		}
	}
	
	public static int size() {
		return size;
	}
	
	public static int empty() {
		if(size == 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
	
	public static int top() {
		if(size == 0) {
			return -1;
		}
		else {
			return stack[size - 1];
		}
	}
	
}
 

 

 

 

워낙 쉬운 문제라.. 자잘한 실수만 안한다면 쉽게 풀 수 있다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23964064  -  방법 2 : BufferedReader + StringBuilder

채점 번호 : 23964062  -  방법 1 : Scanner + StringBuilder

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제는 별달리 설명 할 것이 없었다. 스택 자료구조 자체를 설명한다면 워낙 길어지기 때문에 필자가 자료구조에서 스택 관련 포스팅을 먼저 썼던 이유도 이에 있다.

 

만약 스택에 대해 잘 몰랐다면 한 번쯤은 읽어보셨으면 한다.

혹여 이해하기 어렵거나 잘못된 부분이 있다면 언제든 댓글 달아주시면 된다.