스택, 큐 그리고 우선순위 큐 맛보기

스택 (Stack)

• top : 삽입과 삭제가 일어나는 위치(최상단)

• push : top 위치에 새로운 데이터를 삽입

• pop : top 위치에 있는 데이터를 삭제하고 확인

• peek : top 위치에 있는 데이터를 확인

큐 (Queue)

• rear : 가장 끝 데이터

• front : 가장 앞 데이터

• add : rear 부분에 새로운 데이터를 삽입

• poll : front 부분에 있는 데이터를 삭제하고 확인 (스택의 pop과 유사)

• peek : front에 있는 데이터를 확인

백준 #10828 : 스택

문제

• push X: 정수 X를 스택에 넣는 연산이다.

• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 스택에 들어있는 정수의 개수를 출력한다.

• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

출력

Stack<자료형> stack = new Stack<>();

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

public class Main {

    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());
        String input;
        Stack<Integer> stack = new Stack<>();

        for(int i=0; i<N; i++) {
            input = br.readLine();
            if(input.contains("push ")) {
                int X = Integer.parseInt(input.replace("push ", ""));
                stack.push(X); // PUSH: 값 삽입
            } else if(input.equals("pop")) {
                if(stack.isEmpty()) sb.append("-1").append("\n");
                else sb.append(stack.pop()).append("\n"); // POP: 값 삭제 후 반환
            } else if(input.equals("size")) {
                sb.append(stack.size()).append("\n");
            } else if(input.equals("empty")) {
                sb.append(stack.isEmpty() ? "1" : "0").append("\n");
            } else if(input.equals("top")) {
                if(stack.isEmpty()) sb.append("-1").append("\n");
                else sb.append(stack.peek()).append("\n"); // PEEK: 값 반환
            }
        }

        System.out.println(sb);
    }

}

백준 #10845 : 큐

문제

• push X: 정수 X를 큐에 넣는 연산이다.

• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 큐에 들어있는 정수의 개수를 출력한다.

• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.

• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

출력

Queue<자료형> queue = new LinkedList<>();

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    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());
        String input;
        Queue<Integer> queue = new LinkedList<>();
        int last = 0;

        for(int i=0; i<N; i++) {
            input = br.readLine();
            if(input.contains("push ")) {
                int X = Integer.parseInt(input.replace("push ", ""));
                queue.add(X); //ADD: 값 추가
                last = X;
            } else if(input.equals("pop")) {
                if(queue.isEmpty()) sb.append("-1").append("\n");
                else sb.append(queue.poll()).append("\n"); //POLL: 값 삭제 후 반환
            } else if(input.equals("size")) {
                sb.append(queue.size()).append("\n");
            } else if(input.equals("empty")) {
                sb.append(queue.isEmpty() ? "1" : "0").append("\n");
            } else if(input.equals("front")) {
                if(queue.isEmpty()) sb.append("-1").append("\n");
                else sb.append(queue.peek()).append("\n"); //PEEK: 값 반환
            } else if(input.equals("back")) {
                if(queue.isEmpty()) sb.append("-1").append("\n");
                else sb.append(last).append("\n");
            }
        }

        System.out.println(sb);
    }

}

백준 #2164 : 카드2

문제

입력

출력

예제 입력 1

6

예제 출력 1

4

풀이 방향 설정

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

public class Main {
    public static void main(String[] args) throws IOException {
        int N;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        Queue<Integer> queue = new LinkedList<>();

        for(int i=1; i<=N; i++) {
            queue.add(i);
        }

        while(queue.size() > 1) {
            queue.remove();
            int top = queue.poll();
            queue.add(top);
        }

        System.out.println(queue.peek());


    }

}

• queue.remove() : 위에 있는 카드 버리기

• queue.add(queue.poll) : 위에 있는 카드를 버리고, 해당 카드를 맨 아래에 추가

백준 #9012 : 괄호

문제

입력

출력

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

풀이 방향 설정

• 주어진 문자열에서 한 글자씩 저장

• 만약 추가하려는 문자열이 바로 이전에 저장된 문자열과 짝이 맞는 경우 → 이전에 저장된 문자열 제거

• 위 과정을 반복한 후에 저장된 문자열이 하나도 없을 경우 “올바른 문자열” → “YES” 출력

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

public class Main {

    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());
        String input;

        for(int i=0; i<N; i++) {
            input = br.readLine();

            sb.append(solve(input)).append('\n');
        }

        System.out.println(sb);
    }

    public static String solve(String s) {

        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if(c == '(') {
                stack.push(c);
            }

            else {
                if(stack.empty() || stack.peek() != '(') {
                    return "NO";
                }
                else stack.pop();
            }
        }

        if(stack.empty()) {
            return "YES";
        }
        else {
            return "NO";
        }
    }

} 

우선순위 큐 (Priority Queue)

PriorityQueue<자료형> queue = new PriorityQueue<>

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();

// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

백준 #11286 : 절댓값 힙

문제

1. 배열에 정수 x (x ≠ 0)를 넣는다.

2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

입력

출력

예제 입력 1

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력 1

-1
1
0
-1
-1
1
1
-2
2
0

풀이 방향 설정

PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
            //절댓값 작은 데이터 우선
            int o1_abs = Math.abs(o1);
            int o2_abs = Math.abs(o2);

            //절댓값 같은 경우 음수 우선
            if(o1_abs == o2_abs) {
                return o1 > o2 ? 1 : -1; //첫번째가 더 크면 양수 리턴, 두번째가 더 크면 음수 리턴
            } else {
                return o1_abs - o2_abs; //첫번째 절댓값이 크면 양수 리턴, 두번째 절댓값이 크면 음수 리턴
            }
});

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

public class Main {
    public static void main(String[] args) throws IOException {
        int N;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> 
            int o1_abs = Math.abs(o1);
            int o2_abs = Math.abs(o2);

            if(o1_abs == o2_abs) {
                return o1 > o2 ? 1 : -1;
            } else {
                return o1_abs - o2_abs;
            }
        });

        for(int i=0; i<N; i++) {
            int input = Integer.parseInt(br.readLine());
            if(input==0) {
                if(MyQueue.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(MyQueue.poll());
                }
            } else {
                MyQueue.add(input);
            }
        }

    }

}