[백준] 스택, 큐, 덱_2

서론

---

스택, 큐, 덱 문제 풀이_2

---

4949 : 균형잡힌 세상

---

문제

---

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

---

해설

---

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        while (true) {
            Stack<Character> stack = new Stack<>();
            String input = br.readLine();
            if(input.charAt(0)=='.'){
                break;
            }
            //문자열 길이만큼 반복
            for (int i = 0; i < input.length(); i++) {
            	//문자열의 문자를 확인
                char tmp = input.charAt(i);
                //스택이 비어있는데, 닫는 괄호가 나온다면 균형잡힌 문자열이 아니다.
                if(stack.isEmpty() && (tmp == ')' || tmp == ']')){
                    //밑에서 스택이 비어있는 경우 균형잡힌 문자열로 인식하므로,
                    //의미없는 문자인 n을 스택에 넣는다.
                    stack.push('n');
                    break;
                }
                //여는 괄호일 경우 스택에 넣는다.
                if(tmp == '(' || tmp == '['){
                    stack.push(tmp);
                }
                //스택이 비어있지 않고 소괄호일 때
                else if(!stack.isEmpty() && tmp == ')'){
                    //스택의 맨 위의 요소가 대괄호라면 (매칭되지 않음)
                    if(stack.peek() == '['){
                        //break;를 통해 반복문을 빠져나온다.
                        // 균형잡힌 문자열이 아니기때문에 for문을 더 진행할 필요가 없음
                        break;
                    }
                    //소괄호일 때 맨 위 요소가 소괄호라면 (매칭됨)
                    else {
                    	//스택에서 '('를 pop한다.
                        stack.pop();
                    }
                }
                //스택이 비어있지 않고 대괄호일 때
                else if(!stack.isEmpty() && tmp == ']'){
                    //스택의 맨 위 요소가 소괄호라면 (매칭되지 않음)
                    if(stack.peek() == '('){
                        //위와 마찬가지로 반복문 탈출
                        break;
                    }
                    //대괄호일 때 맨 위 요소가 대괄호라면 (매칭됨)
                    else {
                        //스택에서 '['를 pop한다.
                        stack.pop();
                    }
                }

            }
            //위의 for문을 지나고 나서 스택이 비어 있을 경우 균형잡힌 문자열이다.
            if (stack.isEmpty()) {
                sb.append("yes").append("\n");
            }
            else {
                sb.append("no").append("\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

12789 : 도키도키 간식드리미

---

문제

---

https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

---

해설

---

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < N; i++) {
            q.add(Integer.valueOf(st.nextToken()));
        }
        //1부터 N까지의 번호표가 순서대로 나올 수 있어야 가능한 경우이다.
        for (int i = 1; i <= N; i++) {
            //큐가 비어있지 않고, 큐의 맨 앞 요소가 i일 때
            //즉, 현재 나와야할 번호와 일치하는 경우
            if(!q.isEmpty() && q.peek() == i){
            	//큐에서 해당 번호를 삭제한다.
                q.poll();
            }
            //큐가 비어있는 경우 스택을 확인한다.
            //스택에 역순으로 쌓여있지 않으면 간식을 받을 수 없다.
            else if(q.isEmpty()){
            	//스택의 맨 위 요소가 현재 나와야할 번호인 경우 스택에서 해당 요소를 삭제한다.
                if(s.peek() == i){
                    s.pop();
                }
                //스택의 맨 위 요소가 현재 나와야할 번호가 아닌 경우
                //순서대로 간식을 받을 수 없으므로, 반복문을 종료한다.
                else {
                    break;
                }
            }
            //큐가 비어있지 않고, 스택이 비어있지 않고, 큐의 맨 처음 요소가 현재 번호가 아닌 경우 
            //스택의 맨 위 요소가 현재 나와야 할 번호인 경우
            else if(!s.isEmpty() && s.peek() == i){
            	//스택에서 해당 요소를 삭제한다.
                s.pop();
            }
            //위의 모든 경우가 아닌 경우
            else {
            	//큐에서 스택으로 옮긴다.
                s.push(q.poll());
                //그리고 현재 나와야 할 수가 나온 것이 아니라 스택에 들어간 것이므로
                //i를 하나 줄여준다.
                i--;
            }
        }
        StringBuilder sb = new StringBuilder();
        //큐는 당연히 비어있게 되고
        //마지막에 스택이 비어있는 경우 순서대로 간식을 받을 수 있다.
        if(s.isEmpty()){
            sb.append("Nice");
        }
        else {
            sb.append("Sad");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

18258 : 큐 2

---

문제

---

https://www.acmicpc.net/problem/18258

18258번: 큐 2

---

해설

---

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch (st.nextToken()){
                case "push":
                    deque.add(Integer.valueOf(st.nextToken()));
                    break;
                case "pop":
                    sb.append(deque.isEmpty() ? -1 : deque.poll()).append("\n");
                    break;
                case "size":
                    sb.append(deque.size()).append("\n");
                    break;
                case "empty":
                    sb.append(deque.isEmpty() ? 1 : 0).append("\n");
                    break;
                case "front":
                    sb.append(deque.isEmpty() ? -1 : deque.peekFirst()).append("\n");
                    break;
                case "back":
                    sb.append(deque.isEmpty() ? -1 : deque.peekLast()).append("\n");
                    break;
                default:
                    break;
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

간단하게 switch~case, 3항 연산자를 이용하여 구현하였다.

그리고, 맨 앞 요소, 맨 뒤 요소를 출력하는 명령이 있어서 양방향 큐인 deque를 사용하였다.

---

결론

---

큐와 스택 그리고 덱의 자료구조에 대해 이해하고 있어서, 문제를 푸는 것에 어려움은 없었다.

하지만, 오랜만에 사용해보려니 메서드 사용이 조금 헷갈리는 부분들이 있었던 것 같다.

다음에 이에 대해 정리해보아야 겠다.

---