코딩 테스트 Java 스택 큐 문제 풀이

개요와 목적

코딩 테스트 대표적인 스택 큐 문제들을 풀어보고,

스택 큐의 문제 풀이 방식에 대해서 알아본다.

후위식 연산

352+*9-

---

풀이

후위식이란, 연산만 뒤로 뺀 것이다.

예를 들어 5 -3 은 5 3 - 이렇게 표현한다.

3 5 2 + * 9 -

에서 숫자를 만나면 스택에 넣고, 연산자를 만나면 처음 숫자는 rt로 그 다음 숫자는 lt로 pop해서 알아온다. 그리고 lt 연산자 rt (5+2) 결과를 계산해서, 다시 스택에 넣는다. 이 동작을 반복해서 최종 연산 결과를 구한다.

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

public class 후위식연산 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String next = sc.next();
        char[] chars = next.toCharArray();
        Stack<Integer> stack = new Stack<>();
        for (char x : chars) {
            if(Character.isDigit(x)){
                stack.push(x-48);
            }
            else{
                int rt=stack.pop();
                int lt=stack.pop();
                if(x=='+') stack.push(lt+rt);
                else if(x=='-') stack.push(lt-rt);
                else if(x=='*') stack.push(lt*rt);
                else if(x=='/') stack.push(lt/rt);
            }
        }
        System.out.println(stack.get(0));
    }
}

쇠막대기

10799번: 쇠막대기

풀이

public class 쇠막대기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String next = sc.next();

        //먼저 ()를 .으로 바꿔서 표현하자
        String str = next.replace("()", "_");
        char[] chars = str.toCharArray();

        Stack<Character> stack = new Stack<>();
        // ( 를 만나면, stack에 추가하기
        // _ 레이저를 만나면 stack에 있는 개수만큼 answer에 플러스해주기
        //) 를 만나면 stack에서 제일 위에 것 제거 후 answer +1 해주기
        int answer = 0;
        for (char aChar : chars) {
            if (aChar == '_') {
                answer += stack.size();
            } else if (aChar == '(') {
                stack.push(aChar);
            } else {
                stack.pop();
                answer += 1;
            }
        }
        System.out.println(answer);
    }
}

공주 구하기

8 3

---

풀이

Que에 k-1 번 만큼 que.add(que.poll())을 해서 돌 수 있게 하고.

k번 째 수는 que.poll() 빼버린다. 이런 동작을 que에 값이 1개 남아 있을 때까지 반복 하면 된다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 공주구하기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }
        while (queue.size()!=1) {
            //k-1번 뺀다음 뒤에 다시 넣기
            for (int i = 1; i < k; i++) {
                queue.add(queue.poll());
            }
            //k번 째 수는 뻬머리기
            queue.poll();
        }
        System.out.println(queue.poll());
    }
}

교육 과정 설계

CBA CBDAGE

---

풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 교육과정설계 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        String t = sc.next();

        Queue<Character> queue = new LinkedList<>();
        for (char c : n.toCharArray()) {
            queue.add(c);
        }

        String answer = "YES";
        for (char x : t.toCharArray()) {
            if (queue.contains(x)) {
                //듣는 과목이 큐 안에 있다면
                // 가장 큐의 맨 앞 과목이어야 한다.
                if (x != queue.poll()) {
                    answer = "NO";
                    break;
                }
            }
        }
        //큐가 비어져 있지 않다. 필수 과목을 듣지 않았다
        //그러면 NO 출력
        if (!queue.isEmpty()) {
            answer = "NO";
        }
        System.out.println(answer);
    }
}

응급실

5 2

60 50 70 80 90

6 3

70 60 90 60 60 60

---

풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 응급실 {
    static class Person{
        int id;
        int priority;
        public Person(int id, int priority){
            this.id=id;
            this.priority=priority;
        }
    }

    public static void main(String[] args) {

        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        int answer = 0;
        Queue<Person> Q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            Q.offer(new Person(i, arr[i]));
        }
        while (!Q.isEmpty()) {
            Person tmp = Q.poll();
            for (Person x : Q) {
                if (x.priority > tmp.priority) {
                    Q.offer(tmp);
                    tmp = null;
                    break;
                }
            }
            if (tmp != null) {
                answer++;
                if (tmp.id == m) {
                    break;}
            }
        }
        System.out.println(answer);
    }
}