BOJ 백준온라인져지 10866 덱 풀이

1. 하.. 내가 왜 이걸 Circular Linked List 로 구현했지?

2. head 를 기준으로 l 은 last head 는 first

3. 배열을 쓰면 더 쉬웠을탠데...

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/10866
	* BOJ 백준온라인져지 10866 덱 풀이
	*/
	class Main {
	static class Node {
	public Node l = null, r = null;
	public String n;
	public Node (String n) {
	this.n = n;
	}
	}
	private static Node head = null;
	private static int size = 0;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int N = Integer.parseInt(br.readLine());
	for (int i = 0; i < N; i++) {
	String str = br.readLine();
	String n = "";
	if (str.split(" ").length > 1) {
	n = str.split(" ")[1];
	size++;
	}
	String command = str.split(" ")[0];
	if (command.equals("push_front")) {
	Node first = new Node(n);
	if (size > 1) {
	if (size == 2) {
	head.l = head.r = first;
	first.l = first.r = head;
	} else {
	first.r = head;
	first.l = head.l;
	head.l.r = head.l = first;
	}
	head = first;
	} else head = first;
	} else if (command.equals("push_back")) {
	Node last = new Node(n);
	if (size > 1) {
	if (size == 2) {
	head.l = head.r = last;
	last.l = last.r = head;
	} else {
	last.l = head.l;
	last.r = head;
	head.l = head.l.r = last;
	}
	} else head = last;
	} else if (command.equals("pop_front")) {
	if (size == 0) {
	bw.write("-1");
	} else if (size == 1) {
	bw.write(head.n);
	head = null;
	size--;
	} else {
	bw.write(head.n);
	if (size > 2){
	head.l.r = head.r;
	head.r.l = head.l;
	} else {
	head.l.r = head.l.l = null;
	}
	head = head.r;
	size--;
	}
	bw.write("\n");
	} else if (command.equals("pop_back")) {
	if (size == 0) {
	bw.write("-1");
	} else if (size == 1) {
	bw.write(head.n);
	head = null;
	size--;
	} else {
	bw.write(head.l.n);
	if (size > 2){
	head.l = head.l.l;
	head.l.r = head;
	} else {
	head.r = head.l = null;
	}
	size--;
	}
	bw.write("\n");
	} else if (command.equals("size")) {
	bw.write(String.valueOf(size));
	bw.write("\n");
	} else if (command.equals("empty")) {
	bw.write(size == 0 ? "1" : "0");
	bw.write("\n");
	} else if (command.equals("front")) {
	bw.write(head != null ? head.n : "-1");
	bw.write("\n");
	} else if (command.equals("back")) {
	if (size == 0) {
	bw.write("-1");
	} else if (size == 1) {
	bw.write(head.n);
	} else {
	bw.write(head.l.n);
	}
	bw.write("\n");
	}
	}
	bw.flush();
	}
	}

view raw BOJ_10866.java hosted with ❤ by GitHub

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.