[Coding Test] 자료구조 2

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 보기

---

스택

스택이란?

데이터를 쌓아올린 자료구조로 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 특성

주요 메서드

• push(element): 스택에 데이터를 추가한다.

• pop(): 스택에서 가장 위의 데이터를 제거하고 반환한다.

• peek(): 스택에서 가장 위의 데이터를 반환하되 제거하지는 않는다.

• empty(): 스택이 비어있는지 확인한다.

예시

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.pop()); // 출력: 30
System.out.println(stack.peek()); // 출력: 20

스택은 깊이 우선 탐색(DFS), 백트래킹에서 자주 사용되는 개념이다.

---

큐

큐란?

데이터를 일렬로 나열한 자료구조로 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 특성

주요 메서드

• offer(element): 큐에 데이터를 추가한다.

• poll(): 큐의 앞에서 데이터를 제거하고 반환한다.

• peek(): 큐의 앞에 있는 데이터를 반환하되 제거하지는 않는다.

• isEmpty(): 큐가 비어있는지 확인한다.

예시

Queue<Integer> queue = new LinkedList<>();
queue.offer(10);
queue.offer(20);
queue.offer(30);

System.out.println(queue.poll()); // 출력: 10
System.out.println(queue.peek()); // 출력: 20

큐는 너비 우선 탐색(BFS)에서 자주 사용되는 개념이다.

---

우선순위 큐

우선순위 큐란?

값이 들어간 순서와 관계없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
일반적으로 힙(Heap) 자료구조를 기반으로 구현되며, 자바에서는 PriorityQueue 클래스를 사용한다.

우선순위 큐의 특징

• 기본적으로 최소 힙(Min-Heap) 으로 구성되어 있어, 작은 값부터 우선적으로 꺼내진다.
• Comparator를 이용해 우선순위를 자유롭게 커스터마이징할 수 있다.
• 삽입과 삭제 연산의 시간 복잡도는 O(log N)이다.

주요 메서드

• offer(element): 우선순위 큐에 데이터를 추가한다.
• poll(): 가장 우선순위가 높은 데이터를 제거하고 반환한다.
• peek(): 가장 우선순위가 높은 데이터를 반환하되 제거하지는 않는다.
• isEmpty(): 큐가 비어있는지 확인한다.

예시: 기본 오름차순 우선순위 큐

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);

System.out.println(pq.poll()); // 출력: 1
System.out.println(pq.poll()); // 출력: 2

예시: 사용자 정의 정렬 기준 (절댓값 기준 정렬)

• 백준 11286: 절댓값이 작을수록 우선순위가 높고, 같을 경우 음수를 우선시

PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> {
    int first_abs = Math.abs(o1);
    int second_abs = Math.abs(o2);

    if (first_abs == second_abs) {
        return o1 - o2; // 음수 우선
    }
    return first_abs - second_abs; // 절댓값 작은 순
});

전체 코드 예시 (입력: N개의 정수, 출력: 조건에 맞는 값 순서대로)

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 N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> {
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);

            if (first_abs == second_abs) {
                return o1 - o2;
            }
            return first_abs - second_abs;
        });

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