[백준 알고리즘] 백준 10845번: 큐 / 자바 Java 8 (자료구조, 큐)
🔔 문제
출처 : https://www.acmicpc.net/problem/10845
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (추가 시간 없음) | 256 MB | 68174 | 32653 | 25205 | 49.094% |
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1 복사
15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front
예제 출력 1 복사
1
2
2
0
1
2
-1
0
1
-1
0
3
출처
- 문제를 만든 사람: baekjoon
- 문제의 오타를 찾은 사람: compro0317
알고리즘 분류
🔐 해결 (소스 코드)
import java.util.Scanner;
public class Main {
public static int[] queue;
public static int size = 0;
public static int front = 0;
public static int back = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = sc.nextInt();
queue = new int[N];
for (int i=0; i<N; i++) {
String command = sc.next();
switch (command) {
case "push":
push(sc.nextInt());
break;
case "pop":
sb.append(pop()).append('\n');
break;
case "size":
sb.append(size()).append('\n');
break;
case "empty":
sb.append(empty()).append('\n');
break;
case "front":
sb.append(front()).append('\n');
break;
case "back":
sb.append(back()).append('\n');
break;
}
}
System.out.println(sb);
}
private static void push(int item) {
queue[back] = item;
back++;
size++;
}
private static int pop() {
if (size == 0) {
return -1;
} else {
int result = queue[front];
queue[front] = 0;
size--;
front++;
return result;
}
}
private static int size() {
return size;
}
private static int empty() {
if (size == 0) {
return 1;
} else {
return 0;
}
}
private static int front() {
if (size == 0) {
return -1;
}
else {
return queue[front];
}
}
private static int back() {
if (size == 0) {
return -1;
}
else {
return queue[back - 1];
}
}
}
🧩 배운점
1. back, front 변수를 정의, 이용
back과 front라는 정수형의 변수를 활용해서 push, pop, front, back 함수를 구현하는 것을 통해서 새로운 시각이 열렸다.
파이썬으로 구현했을 때는 deque 이라는 라이브러리를 이용해서 구현해서 풀었다보니 그냥 갖다 쓰기만 해서 비교적 쉬웠다.
자바로는 Scanner와 StringBuilder만을 이용해서 문제에서 원하는 방향대로 직접 구현해보려고 애썼는데, 그 핵심 포인트가 back과 front 변수를 적극 활용하는 것이었다.
하지만, 분명히 다른 좋은 방법이 있을 것 같다.
이 문제와 거의 똑같은 문제인 큐 2 문제에서는 똑같은 코드로 정답처리가 되기는 했으나, 속도나 메모리를 많이 먹는 모습을 목격했기 때문이다.알고리즘을 효율적으로 풀고, 더 난이도 높은 문제를 풀기 위해서… 또 더 좋은 개발자가 되기 위해서는 정말 많이 성장해야될 것 같다. 갈 길이 멀다. 화이팅 ㅠㅠ 💪
Leave a comment