백준 10828번 스택

문제

링크 : https://www.acmicpc.net/problem/10828

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < n; i++) {
            String str = sc.next();
            if(str.contains("push")) {
                stack.push(sc.nextInt());
            } else if(str.contains("pop")) {
                if(stack.isEmpty()) {
                    sb.append("-1\n");
                } else {
                    sb.append(stack.pop()).append("\n");
                }
            } else if(str.contains("size")) {
                sb.append(stack.size()).append("\n");
            } else if(str.contains("empty")) {
                if(stack.isEmpty()) {
                    sb.append("1\n");
                } else {
                    sb.append("0\n");
                }
            } else if(str.contains("top")) {
                if(stack.isEmpty()) {
                    sb.append("-1\n");
                } else {
                    sb.append(stack.peek()).append("\n");
                }
            }
        }

        System.out.println(sb);
    }
}

스택 라이브러리를 사용해서 구현하였다.

결과

백준 9093번 단어 뒤집기

문제

링크 : https://www.acmicpc.net/problem/9093

나의 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < t; i++) {
            String str = br.readLine() + "\n";
            Stack<Character> stack = new Stack<>();
            for(char c : str.toCharArray()) {
                if(c == ' ' || c == '\n') {
                    while(!stack.isEmpty()) {
                        bw.write(stack.pop());
                    }
                    bw.write(c);
                } else {
                    stack.push(c);
                }
            }
        }
        bw.flush();
    }
}

공백이거나 개행 문자일 경우 스택에 있는 모든 문자를 pop해서 역순으로 출력하게 하고 아닌 경우에는 스택에 문자를 추가시키게 구현하였다.

결과

백준 9012번 괄호

문제

링크 : https://www.acmicpc.net/problem/9012

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        for(int i = 0; i < t; i++) {
            String str = sc.next();
            Stack<Character> stack = new Stack<>();
            boolean flag = true;
            for(char c : str.toCharArray()) {
                if(c == '(') {
                    stack.push(c);
                } else {
                    if(stack.isEmpty()) {
                        flag = false;
                        break;
                    }
                    stack.pop();
                }
            }
            if(!stack.isEmpty()) {
                flag = false;
            }
            if(flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

여는 괄호라면 스택에 넣고, 닫는 괄호일 경우 스택이 비어있다면 짝이 안맞는다는 뜻이므로 올바른 괄호 여부를 나타내는 flag 변수를 false로 지정한다. 스택이 비어있지않다면 pop으로 요소를 하나 뺀다. 문자열을 모두 탐색하고 난 후인데도 스택이 비어있지 않다면 짝이 맞지 않다는 뜻이므로 flag를 false로 지정한다. 마지막엔 flag가 true인 경우 YES를 출력하고 아니면 NO를 출력하게 구현하였다.

결과

백준 1874번 스택 수열

문제

링크 : https://www.acmicpc.net/problem/1874

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        StringBuilder sb = new StringBuilder();
        int index = 0;
        for(int x : arr) {
            if(x > index) {
                while(x > index) {
                    stack.push(++index);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            } else {
                if(stack.peek() != x) {
                    System.out.println("NO");
                    return;
                }
                stack.pop();
                sb.append("-\n");
            }
        }
        System.out.println(sb);
    }
}

스택에 넣을 수를 index 변수로 정한다. index는 0부터 시작되는데 입력 받은 숫자가 index 보다 큰 경우 index 보다 작아질 때 까지 stack에 ++index 값을 push한다. 그리고 + 문자열을 sb에 추가한다. while문이 끝나면 입력 받은 숫자랑 같은 숫자를 스택에서 pop시키고 - 문자열을 추가한다. 만약 입력 받은 숫자가 index 보다 작은 경우에는 스택의 top 값이 입력 받은 값과 다른 경우는 수열이 성립하지 않는다는 뜻이므로 NO를 출력시키고 종료한다. 같은 경우에는 해당 숫자를 스택에서 pop 시키고 - 문자열을 추가하게 구현하였다.

결과