[알고리즘] 스택 문제 풀이(백준 9012번, 10773번, 10828번)

bobo12 2023. 8. 3. 11:37

728x90

1. 괄호(백준 9012번)

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

▷ 풀이 코드

import java.awt.desktop.SystemSleepEvent;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class GwalHo {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		
		for(int i=0; i<n; i++) {
			String input = br.readLine();
						
			int a = 0;
			int b = 0;
			
			for(int j=0; j < input.length(); j++) {
				if(input.charAt(j) == '(') {
					a++;
				} else {
					b++;
				}
				
				if(a<b) break;
			}
			
			if(a == b) {
				sb.append("YES").append("\n");
			} else {
				sb.append("NO").append("\n");
			}
		}
		System.out.println(sb);
	}
	
}

◎ 스택 함수를 이용했을 때

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class GwalHo2 {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		
		int n = Integer.parseInt(br.readLine());
		
		
		for(int i=0; i<n; i++) {
			String input = br.readLine();
			
			Stack<Character> s = new Stack<>();
						
			int a = 1;
			
			for(int j=0; j < input.length(); j++) {
				if(input.charAt(j) == '(') {
					s.push(input.charAt(j));
					
				} else {
					
					if(s.empty()) {
						a = 0;
						break;
					}
					s.pop();		

				}
			}					
			
			if(a == 0 || s.size() > 0) {
				sb.append("NO").append("\n");
			} else {
				sb.append("YES").append("\n");
			}
		}
		System.out.println(sb);
	}
}

2. 제로(백준 10773번 문제)

10773번: 제로 (acmicpc.net)

10773번: 제로

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경

www.acmicpc.net

▷ 풀이 코드

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

public class StackZero {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// stack 내장 함수 사용하기
		Stack<Integer> s = new Stack<>();

			int k = sc.nextInt();
			int a;
			int sum = 0;

			for(int i=0; i<k; i++) {
				do {
					a = sc.nextInt();

					if(a == 0) {
						sum -= s.pop();
					} else {

					sum += s.push(a);
					}

				} while(a > 100000 && a < 1);
			}
		System.out.println(sum);
	}
}

3. 스택(백준 10828번 문제)

10828번: 스택 (acmicpc.net)

10828번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

▷ 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Stack {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());

		int[] arr = new int[n];
		int ptr = 0;
		String a;

		for(int i=0; i<n; i++) {
			a = br.readLine();

			switch(a) {
				case "top" :
					if(ptr == 0) System.out.println(-1);
					else System.out.println(arr[ptr - 1]);
					break;
				case "pop" :
					if(ptr == 0) System.out.println(-1);
					else System.out.println(arr[--ptr]);
					break;
				case "size" : System.out.println(ptr);
					break;
				case "empty" :
                    if(ptr == 0) System.out.println(1);
					else System.out.println(0);
					break;
				default :
					if(a.substring(0, 4).equals("push")) {
						arr[ptr++] = Integer.parseInt(a.substring(5));
					}
					break;
			}
		}
		br.close();
	}
}

◎ 스택 함수를 이용했을 때

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class StackEx {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
				
		Stack<Integer> stack = new Stack<>(); 
		
		int num = Integer.parseInt(br.readLine());
		
			
		for(int i=0; i<num; i++) {
			String behav[] = br.readLine().split(" ");
			
			switch (behav[0]) {
			case "push": 
				stack.add(Integer.parseInt(behav[1]));
				break;
			case "pop" : 
				sb.append(stack.isEmpty()?-1:stack.pop()).append("\n");
				break;
			case "size" : sb.append(stack.size()).append("\n");
				break;
			case "empty" : sb.append(stack.isEmpty()?1:0).append("\n");
				break;
			case "top" : sb.append(stack.isEmpty()?-1:stack.peek()).append("\n");
				break;
			}
		}
		System.out.println(sb);

	}
}

이번에는 알고리즘 스터디를 통해 배운 스택을 통해 백준 문제 풀이를 해보았습니다!!

스택의 FIFO 구조를 이용하면 좀 더 간편하게 값을 저장하고 출력할 수 있어요!!

많은 분들의 피드백은 언제나 환영합니다! 많은 댓글 부탁드려요~~

728x90