오늘의 학습 키워드 및 문제
#큐 #Queue #ArrayDeque #LinkedList #PriorityQueue
백준 실버4) 큐
문제풀이
큐 클래스에 있는 메서드 기능들을 알면 그리 어려운 문제는 아니었다.
스택 문제와 비슷하게 풀어냈다.
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));
StringBuilder sb = new StringBuilder();
ArrayDeque<Integer> queue = new ArrayDeque<>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
switch(st.nextToken()) {
case "push":
queue.offer(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\n");
break;
case "size":
sb.append(queue.size()).append("\n");
break;
case "empty":
sb.append(queue.isEmpty() ? 1 : 0).append("\n");
break;
case "front":
sb.append(queue.isEmpty() ? -1 : queue.getFirst()).append("\n");
break;
case "back":
sb.append(queue.isEmpty() ? -1 : queue.getLast()).append("\n");
break;
default:
break;
}
}
System.out.println(sb);
br.close();
}
}Queue
✒️ add() 와 offer() 의 차이
add() 와 offer() 는 값을 추가하는 기능을 가지고 있다.
그런데 같은 기능을 두 개 가지고 있을 필요가 있을까?
둘의 차이를 알아보기로 했다.
두 메서드는 새로운 요소를 추가하는 역할을 하지만 동작 방식이 다르다.
가장 큰 차이점은 예외(Exception) 발생 여부에 있다.
- add(E e)
- 성공하면 true 반환
- Queue가 가득 차면 예외 발생 (IllegalStateException)
- Queue가 가득 찰 일이 없을 때 적절
- 예외 발생을 원할 때 적절
- offer(E e)
- 성공하면 true 반환, 실패하면 false 반환
- 큐가 가득 차도 예외 발생 안함
- Queue가 가득 찰 가능성이 있을 때 적절
- 실패를 예상하고 대비할 때 적절
✒️ ArrayDeque , LinkedList , PriorityQueue 차이
세 클래스 모두 Queue 인터페이스를 구현한 클래스들이지만 내부 동작 방식과 사용 목적이 다르다.
ArrayDeque
- 배열을 기반으로 하는 Deque(Double-Ended-Queue) 구현체
- FIFO(Queue)와 LIFO(Stack) 모두 가능
- 중간 삽입/삭제가 비효율적
- 앞뒤 삽입/삭제는 빠름
- 내부적으로 Resizable Array(크기가 자동 조절되는 배열) 사용
- LinkedList 보다 메모리 사용량이 적음 (노드 객체 따로 만들 필요 없음)
- 앞/뒤 삽입/삭제 O(1)
- 중간 삽입/삭제 O(N) (배열을 이동하기 때문)
- 빠른 앞/뒤 삽입 및 삭제가 필요할 때 적절 (ex. Deque를 이용한 BFS)
LinkedList
- 이중 연결 리스트(Dobly Linked List) 기반 Queue
- 중간 삽입/삭제가 필요할 때 유리
- 메모리 사용량이 상대적으로 많음
- 노드 기반으로 동작 (배열이 아니라 객체들이 연결된 형태)
- ArrayDeque 보다 메모리를 더 많이 사용함 (각 노드가 추가적인 포인터를 가짐)
- Deque 인터페이스를 구현해서 ArrayDeque와 비슷하게 사용 가능
- 앞/뒤 삽입/삭제 O(1)
- 중간 삽입/삭제 O(1)~O(N) (리스트를 순회해서 위치를 찾아야 함)
- 중간 삽입/삭제가 빈번한 경우 적절
- 데이터 크기가 변동이 심하고 크기 예측이 어려운 경우 적절 (배열보다 유연)
PriorityQueue
- 우선순위가 높은 요소가 먼저 나오는 Queue
- Heap(힙) 자료구조 기반
- FIFO가 아닌 우선순위 순서대로 정렬됨
- 내부적으로 Min Heap(기본 : 작은 값) 나옴
- 요소가 들어올 때마다 자동으로 정렬됨
- 앞/뒤 삽입/삭제 O(log N) (힙 정렬 때문)
- 중간 삽입/삭제 불가능 (힙 구조는 중간 삽입 개념이 없음)
- 항상 최댓값 또는 최솟값을 따르게 찾아야 할 때 적절
- 우선순위가 중요한 작업 스케줄링, 경로 탐색이 필요할 때 적절
Please, Steadily