기본적인 스택 구현

💡 백준 10828번 - 구현

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

스택의 메소드는 다음과 같다.

• top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
• pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
• push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
• empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.
• size(): 스택의 크기를 반환한다.

이를 바탕으로 백준 10828번을 구현해보았다.

▼▼▼
백준 10828번 문제 보러가기

자바로 구현하였고, Stack class를 따로 구현하였다.

소스코드 먼저 보여주고 설명하는 편이 빠를 것 같아 일단 소스코드를 첨부한다.

소스코드

import java.util.Scanner;

/*
 * Stack 기본 구현
 * 백준 10828번
 * 
 * Coded by NANAEU	(2021.07.15)
 */

class Stack{
	private int top;
	private int[] stack;
	
	public Stack(int size) {
		this.stack = new int[size];
		this.top = -1;
	}
	
	public void push(int x) {
		this.stack[++top] = x;
	}
	
	public int pop() {
		if(top == -1) return -1;
		return this.stack[top--];
	}
	
	public int size() {
		return top+1;
	}
	
	public int empty() {
		if(top == -1) return 1;
		return 0;
	}
	
	public int top() {
		if(top == -1) return -1;
		return this.stack[top];
	}
	
}

public class Main {
		
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		int N = scan.nextInt();
		
		Stack stack = new Stack(N);
		
		String cmd;
		
		for(int i=0 ; i<N ; i++) {
			
			// 명령 입력
			cmd = scan.next();
			
			switch(cmd) {
			case "push":
				stack.push(scan.nextInt());
				break;
			case "pop":
				sb.append(stack.pop()).append("\n");
				break;
			case "top":
				sb.append(stack.top()).append("\n");
				break;
			case "size":
				sb.append(stack.size()).append("\n");
				break;
			case "empty":
				sb.append(stack.empty()).append("\n");
				break;
			}
		}
		
		System.out.println(sb);
		
		scan.close();
	}
}

처음에는 Main 클래스의 메인함수에서 각 명령어를 입력받을 때마다 switch문에서 바로바로 System.out.println()으로 출력해주었으나, 시간제한이 빡빡한 편이라 시간초과가 났다. 그래서 StringBuilder를 활용하였다. 결과는 성공!

여기서 쓰인 StringBuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아닌, 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르고 상대적으로 부하가 적어 성능이 좋은 편이다.

pop, top, size, empty는 쉽게 구현했지만 push 명령을 입력받았을 때 그 옆에 공백을 기준으로 나오는 숫자를 어떻게 입력받을지 고민했던 것 같다. (StringTokenizer로 자를까, split 함수를 쓸까, ...) 결론은 명령을 scan.next()로 입력 받고, push 명령이 들어왔다면 scan.nextInt()로 공백 다음에 들어오는 숫자를 따로 입력받았다. 자세한 건 Scanner 클래스 설명 참고!

이렇게 스택의 기본 구조를 구현해보았다. 다음으로는 스택을 활용한 백준 9012번을 풀면서 익혔다.

스택 활용 - 괄호문자열(VPS)

💡 백준 9012번 - 활용

대표적인 스택 활용문제, 괄호문자열(VPS)이다.
주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내는 문제이다.

▼▼▼
백준 9012번 문제 보러가기

소스코드

import java.util.Scanner;
import java.util.Stack;

/*
 * Stack 활용 - VPS(괄호문자열)
 * Stack 클래스 사용
 * 백준 9012번 풀이
 * 
 * Coded by NANAEU	(2021.07.16)
 */

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		
		for(int i=0 ; i<n ; i++)
			System.out.println(solution(scan.next()));
		
	}
	
	public static String solution(String s) {
		
		Stack<Character> stack = new Stack<>();
			
		for(int i=0 ; i<s.length() ; i++) {
			char c = s.charAt(i);
			if(c == '(') {
				stack.push('(');
			}
			else if(c == ')') {
				if(stack.isEmpty()) return "NO";
				else stack.pop();
			}
		}
		
		if(stack.isEmpty()) return "YES";
		else return "NO";
		
	}
}

• '('이 들어오면 PUSH
• ')'이 들어오면 POP

위 규칙을 기본으로, 예외상황 발생 시 "NO"로 나타내주었다.

여기서 예외상황이란 다음과 같다.

1. ')'를 입력받았는데 스택이 비어있을 경우 = ')'갯수가 더 많은 경우 또는 '(' 없이 ')'가 먼저 나왔을 경우
2. 문자열을 모두 입력받았는데 스택이 비어있지 않을경우 = '(' 갯수가 더 많은 경우, 즉 괄호가 다 닫히지 않은 경우

위 문제는 시간제한이 빡빡하지 않았고, 결과는 성공이다.

마치며...

사실 푼 지 시간이 좀 지나긴 했는데, 정리를 해가면서 문제풀이를 해야할 것 같아 지금이라도 글을 올린다. 자료구조 처음부터 익혀가며 기초를 탄탄히 하면 나중에는 어려운 문제들도 잘 풀 수 있으리라 믿는다...😂