1Page 노트정리 큐
1 Page 노트 정리
큐(Queue)
큐는 데이터를 꺼낼 때 항상 첫 번째에 저장된 데이터를 삭제하는 구조를 가지며, ArrayList와 같은 배열 기반 클래스를 사용하면 비효율적입니다.
이는 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하기 때문입니다.
따라서, 데이터의 추가 및 삭제가 쉬운 LinkedList로 큐를 구현하는 것이 더 적합합니다.
큐 선언하기
import java.util.Queue;
import java.util.LinkedList;
Queue queue = new LinkedList(); // Queue 인터페이스의 구현체인 LinkedList를 사용
Queue의 메서드
| 메서드 | 설명 |
|---|---|
boolean add(Object o) |
지정된 객체를 Queue에 추가한다. (저장공간이 부족하면 IllegalStateException 발생) |
Object remove() |
Queue에서 객체를 꺼내 반환한다. (비었으면 NoSuchElementException 발생) |
Object element() |
삭제 없이 요소를 읽어 온다. (peek와 달리 Queue가 비었을 때 NoSuchElementException 발생) |
boolean offer(Object o) |
Queue에 객체를 저장한다. |
Object poll() |
Queue에서 객체를 꺼내서 반환한다. (저장된 것은 삭제된다. 비어있으면 null 반환) |
Object peek() |
삭제 없이 요소를 읽어 온다. (비어있으면 null 반환) |
메서드의 차이점 정리
큐의 메서드는 비슷해 보이지만, 예외 발생 여부와 반환값에서 차이가 있습니다.
| 예외 발생 | 값 반환 | |
|---|---|---|
| 추가 | add() |
offer() |
| 삭제 | remove() |
poll() |
| 읽기 | element() |
peek() |
- 추가 메서드
add(): 큐에 값을 추가하려고 할 때 큐가 꽉 차 있으면 예외(IllegalStateException)를 발생시킵니다.offer(): 큐에 값을 추가하려고 할 때 큐가 꽉 차 있으면 false를 반환합니다.
- 삭제 메서드
remove(): 큐에서 값을 꺼내고 반환합니다. 큐가 비어 있으면 예외(NoSuchElementException)를 발생시킵니다.poll(): 큐에서 값을 꺼내고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
- 읽기 메서드
element(): 큐의 앞에 있는 값을 삭제하지 않고 읽어옵니다. 큐가 비어 있으면 예외(NoSuchElementException)를 발생시킵니다.peek(): 큐의 앞에 있는 값을 삭제하지 않고 읽어옵니다. 큐가 비어 있으면 null을 반환합니다.
이처럼 각 메서드는 큐의 상태에 따라 예외를 발생시키거나 null 혹은 false를 반환하는 방식으로 동작합니다.
상황에 맞게 적절한 메서드를 선택하여 사용하는 것이 중요합니다.
회전하는 큐
문제 설명
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있습니다. 이 큐에서 몇 개의 원소를 뽑아내려고 합니다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있습니다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가
a1, ..., ak였던 것이a2, ..., ak와 같이 됩니다. - 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면,
a1, ..., ak가a2, ..., ak, a1이 됩니다. - 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면,
a1, ..., ak가ak, a1, ..., ak-1이 됩니다.
큐에 처음에 포함되어 있던 수 N이 주어집니다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어집니다. (이 위치는 가장 처음 큐에서의 위치입니다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄: 큐의 크기
N과 뽑아내려고 하는 수의 개수M이 주어진다.N은 50보다 작거나 같은 자연수M은N보다 작거나 같은 자연수
- 둘째 줄: 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다.
- 위치는 1보다 크거나 같고,
N보다 작거나 같은 자연수
- 위치는 1보다 크거나 같고,
출력
- 첫째 줄: 문제의 정답을 출력한다.
예제 입력 1
10 3
1 2 3
예제 출력 1
0
예제 입력 2
10 3
2 9 5
예제 출력 2
8
예제 입력 3
32 6
27 16 30 11 6 23
예제 출력 3
59
예제 입력 4
10 10
1 6 3 2 7 9 8 4 10 5
예제 출력 4
14
문제 풀이
이 문제는 원형 큐에서 특정 요소를 꺼내기 위해 최소한의 이동 횟수를 구하는 것입니다.
문제에서 지민이가 큐의 특정 위치에 있는 원소를 순서대로 꺼내야 하는데, 이를 위해 큐를 왼쪽 또는 오른쪽으로 회전시키는 최소 횟수를 계산하는 것이 핵심입니다.
접근 방법
초기화: 큐에 1부터 N까지의 값을 저장합니다. 이 큐는 양방향으로 회전할 수 있어야 하므로, LinkedList를 사용합니다.
입력 처리: 꺼내야 할 값의 위치를 입력받습니다.
값 꺼내기: 각 값을 꺼내기 위해 큐를 회전시키고, 회전할 때마다 필요한 최소 이동 횟수를 계산합니다.
이유
LinkedList는 양방향으로 회전하는 데 유리합니다.
첫 번째 값을 왼쪽으로 회전시키면 맨 뒤로 이동하고, 마지막 값을 오른쪽으로 회전시키면 맨 앞으로 이동합니다.
이는 LinkedList의 메서드인 addFirst, addLast, removeFirst, removeLast를 통해 쉽게 구현할 수 있습니다.
큐의 크기 N이 최대 50으로 작기 때문에 LinkedList를 사용한 회전 연산의 복잡도는 허용 범위 내에 있습니다.
각 값을 꺼낼 때 최소 이동 횟수를 계산해야 합니다.
이를 위해 목표 값이 큐의 어느 쪽에 더 가까운지 판단하고, 그 방향으로 회전시킵니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class BJ1021 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
LinkedList<Integer> Deq = new LinkedList<Integer>();
//LinkesList에 1부터 N값까지 순서대로 저장한다.
for (int i = 1; i <= N; i++) {
Deq.add(i);
}
//이동 횟수를 저장 할 변수
int count = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
//num값이 맨 앞에 올때까지 반복한다.
while (Deq.getFirst() != num) {
if (Deq.indexOf(num) <= (Deq.size() / 2)) {
Deq.addLast(Deq.getFirst());
Deq.removeFirst();
} else {
Deq.addFirst(Deq.getLast());
Deq.removeLast();
}
count++;
}
//num값이 맨 앞에 위치하면 그 값을 제외시킨다.
if (Deq.getFirst() == num) {
Deq.removeFirst();
}
}
System.out.println(count);
}
}
출처 : 백준, https://www.acmicpc.net/problem/1021
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발 속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(
progresses,speeds배열의 길이)는 100개 이하입니다. - 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
| progresses | speeds | return |
|---|---|---|
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
입출력 예 설명
입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다. 두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다. 세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.
따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42586
Leave a comment