[백준] 10866번 덱 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
19. 큐, 덱
큐와 덱을 구현하고 사용해 봅시다.
큐와 덱을 구현하고 사용해 봅시다.
Java / Python
5. 덱
덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.)
이번 문제는 덱을 구현하는 문제입니다. 덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태입니다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있으며, 큐와 스택을 합친 형태로 생각할 수 있습니다.
- Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args) throws IOException {
ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
switch (s[0]) {
case "push_front": {
deque.addFirst(Integer.parseInt(s[1]));
break;
}
case "push_back": {
deque.addLast(Integer.parseInt(s[1]));
break;
}
case "pop_front": {
if (deque.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(deque.pollFirst()).append('\n');
}
break;
}
case "pop_back": {
if (deque.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(deque.pollLast()).append('\n');
}
break;
}
case "size": {
sb.append(deque.size()).append('\n');
break;
}
case "empty": {
if (deque.isEmpty()) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
break;
}
case "front": {
if (deque.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(deque.peekFirst()).append('\n');
}
break;
}
case "back": {
if (deque.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(deque.peekLast()).append('\n');
}
break;
}
}
}
System.out.println(sb);
}
}
- Python
import sys
from collections import deque
N = int(sys.stdin.readline())
dq = deque()
def size():
return len(dq)
def empty():
if len(dq) == 0:
return 1
else :
return 0
for _ in range(N):
s = list(sys.stdin.readline().split())
if s[0] == 'push_front':
dq.appendleft(s[1])
elif s[0] == 'push_back':
dq.append(s[1])
elif s[0] == 'pop_front':
if empty() == 1:
print("-1")
else:
tmp = dq.popleft()
print(tmp)
elif s[0] == 'pop_back':
if empty() == 1:
print("-1")
else:
tmp = dq.pop()
print(tmp)
elif s[0] == 'front':
if empty() == 1:
print("-1")
else:
print(dq[0])
elif s[0] == 'back':
if empty() == 1:
print("-1")
else:
print(dq[len(dq)-1])
elif s[0] == 'size':
print(size())
elif s[0] == 'empty':
print(empty())
Author And Source
이 문제에 관하여([백준] 10866번 덱 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-10866번-덱-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)