Queue(큐) 기본 구현
Queue(큐)란?
먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 자료구조. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
큐는 put(insert)와 get(delete)을 이용하여 구현된다. put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다! front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다. 또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.
💡 백준 18258번 - 구현
백준 18258번으로 큐의 기본 구조를 자바로 구현하였다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;
/*
* Queue 기본 구현
* 백준 18258번 풀이
* 참고 : https://st-lab.tistory.com/186
* LinkedList 방식
*
* Coded by NANAEU (2021.07.15)
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Deque<Integer> queue = new LinkedList<>();
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int i=0 ; i<N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
switch(st.nextToken()) {
case "push":
queue.offer(Integer.parseInt(st.nextToken()));
break;
case "pop":
if(queue.size() == 0)
sb.append(-1).append('\n');
else
sb.append(queue.poll()).append('\n');
break;
case "size":
sb.append(queue.size()).append('\n');
break;
case "empty":
if(queue.isEmpty())
sb.append(1).append('\n');
else
sb.append(0).append('\n');
break;
case "front":
if(queue.isEmpty())
sb.append(-1).append('\n');
else
sb.append(queue.peekFirst()).append('\n');
break;
case "back":
if(queue.isEmpty())
sb.append(-1).append('\n');
else
sb.append(queue.peekLast()).append('\n');
break;
}
}
System.out.println(sb);
}
}이 문제 또한 스택의 기본 구현 - BOJ 10828번처럼 시간제한이 빡빡했던 문제다. 그래서 입력을 Scanner가 아닌 BufferedReader로 받고, 명령에 대한 처리는 StringBuilder와 StringTokenizer를 활용했다. 부끄럽지만 처음에 시간초과가 날 때 어떻게 처리해줘야할까 고민하다가 잘 모르겠어서... 소스코드 상단에 있는 링크의 게시물을 참고하여 시간초과를 처리해주었다.
여기서 구현한 큐의 메소드는 push, pop, size, empty, front, back(rear)이다.
- push = add : 해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생
- pop = poll : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
- size : 해당 큐의 크기를 반환한다.
- empty : 해당 큐가 비었는지에 대한 여부를 반환한다.
- front : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
- back = rear : 해당 큐의 맨 뒤에 있는(제일 나중에 저장된) 요소를 반환함.
Queue(큐) 활용 - 주차장
💡 백준 5464번 - 활용
문제에 대한 설명은 아래 링크를 참고.
▼▼▼
백준 5464번 문제 보러가기
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;
/*
* Queue 활용
* 백준 5464번 풀이
*
* 대기차량 - 큐
* 주차장의 주차여부 - int 배열[N]
* 주차료 = 차량무게 * 주차공간별 단위무게당 요금
* 총 M대의 차량이 정해진 순서에 따라 주차장 이용 예정 (1번 ~ M번)
*
* 주어지는 조건 : 주차공간별 요금, 차량들의 무게, 출입순서
* 결과 : 오늘 총 수입액
*
*
* Coded by NANAEU (2021.07.15)
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str);
int sum = 0; // 총 수입
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 주차장 - 주차된 차량번호 저장 예정
int[] parked = new int[N];
for(int i=0 ; i<N ; i++)
parked[i] = 0;
// 주차 공간들의 단위무게당 요금
int[] cost = new int[N];
for(int i=0 ; i<N ; i++) {
str = br.readLine();
cost[i] = Integer.parseInt(str);
}
// 차량들의 무게
int[] weight = new int[M];
for(int i=0 ; i<M ; i++) {
str = br.readLine();
weight[i] = Integer.parseInt(str);
}
Deque<Integer> q = new LinkedList<>(); // 주차장 출입순서
Deque<Integer> waiting = new LinkedList<>(); // 대기차량
for(int i=0 ; i<2*M ; i++) {
str = br.readLine();
int value = Integer.parseInt(str);
q.add(value);
}
int cnt = 0; // 현재 주차된 개수
while(!q.isEmpty()) {
if(q.peekFirst() > 0) {
if(cnt < N) {
for(int i=0 ; i<N ; i++) {
if(parked[i] == 0) {
// 주차
/* TEST */
// System.out.println("<< 주차 >> : " + q.peekFirst());
parked[i] = q.poll();
break;
}
}
cnt++;
}
else {
// 주차장이 꽉 찼을 경우 대기 큐로 빼자
waiting.add(q.poll());
}
}
if(q.peekFirst() < 0) {
/* TEST */
// System.out.println(">> 주차해제 << : " + q.peekFirst());
int num = q.peekFirst() * (-1);
for(int i=0 ; i<N ; i++) {
if(parked[i] == num) {
// 주차장에서 빠져나감
parked[i] = 0;
// 주차요금 계산
sum += weight[num-1] * cost[i];
q.poll();
}
}
cnt--;
// 대기차량 주차
if(!waiting.isEmpty()) {
for(int i=0 ; i<N ; i++) {
if(parked[i] == 0) {
/* TEST */
// System.out.println("<< 대기차량 주차 >> : " + waiting.peekFirst());
parked[i] = waiting.poll();
break;
}
}
cnt++;
}
}
/* TEST */
// System.out.println("------TEST------");
// Object[] remain = q.toArray();
// for(int i=0 ; i< q.size() ; i++)
// System.out.println(remain[i]);
}
System.out.println(sum);
}
}
문제에 대한 조건만 잘 정리하면 간단한 문제였다. 이 문제에서는 큐를 총 2개로 만들어주었다.
- 주차장 출입순서
- 대기차량
그 외에 주차장에 특정위치에 주차된 차량번호를 저장하는 것, 주차 공간들의 단위무게당 요금, 차량들의 무게는 정수 배열로 만들었고, 현재 주차된 차량의 개수도 int형 변수로 선언해주었다.
이렇게 기본 준비를 마치고 본격적인 주차장 운영을 시작할 때 그 알고리즘 구조를 설명하면 이렇다.
- 만약 양수를 입력받았을 경우, 즉 주차하려는 차량이 들어온 경우
1.1 현재 주차장이 꽉 찼는지 확인 후, 비어있는 자리가 있다면 그곳에 주차하고 꽉 찼다면 대기차량으로 돌린다. - 만약 음수를 입력받았을 경우, 즉 주차했던 차량이 빠져나가는 경우
2.1 주차요금을 계산한다.
2.2 대기차량이 있다면 방금 빠진 자리에 주차한다.
위와 같은 절차로 주차장을 운영하였다.
주차장 출입순서 또는 대기차량 큐에서 처리가 완료된 요소는 poll()처리 해주었다. 결과는 성공!
마치며...
이것도 푼 지 시간이 조금 지나긴 했다...ㅎㅎ 강박감을 가지면 난 더 안 쓴다는 걸 알기에 적당히 흥미를 잃지 않고 밀리지 않을 정도로만 차차 업로드할 예정이다. 아자아자 파이팅 ^.^
