[Java] baekjoon_10866 : 덱

구현, 자료 구조, 덱

덱 : Silver4

https://www.acmicpc.net/problem/10866

10866번: 덱

 

풀이

import java.io.*;
import java.util.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {

    int N = Integer.parseInt(br.readLine());

    Deque<Integer> d = new LinkedList<>();

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String input = st.nextToken();
      int num = 0;

      switch (input) {
        case "push_front":
          num = Integer.parseInt(st.nextToken());
          d.offerFirst(num);
          break;

        case "push_back":
          num = Integer.parseInt(st.nextToken());
          d.offerLast(num);
          break;

        case "pop_front":
          if (!d.isEmpty()) {
            bw.write(String.valueOf(d.pollFirst()));
          } else {
            bw.write("-1");
          }
          break;

        case "pop_back":
          if (!d.isEmpty()) {
            bw.write(String.valueOf(d.pollLast()));
          } else {
            bw.write("-1");
          }
          break;

        case "size":
          bw.write(String.valueOf(d.size()));
          break;

        case "empty":
          if (d.isEmpty()) {
            bw.write("1");
          } else {
            bw.write("0");
          }
          break;

        case "front":
          if (!d.isEmpty()) {
            bw.write(String.valueOf(d.peekFirst()));
          } else {
            bw.write("-1");
          }
          break;

        case "back":
          if (!d.isEmpty()) {
            bw.write(String.valueOf(d.peekLast()));
          } else {
            bw.write("-1");
          }
          break;

        default:
          break;
      }

      if (!input.startsWith("push")) {
        bw.newLine();
      }

    }
    bw.newLine();
    bw.close();
  }
}

 

 

 

Deque

Deque는 "Double Ended Queue"의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다. Deque는 큐(Queue)와 스택(Stack)의 특성을 모두 가지고 있으며, Java에서는 Deque 인터페이스를 제공한다.

Deque 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.

 

 

https://miro.medium.com/v2/resize:fit:1400/format:webp/1*FUh1NionDrsK1vflgfBYPg.png

 

Deque 인터페이스의 메소드는 다음과 같다.

 

addFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다.

 

offerFirst()

덱의 앞쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다. 

 

addLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생한다.

add()와 동일한 동작이다.

 

offerLast()

덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다. 

 

removeFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. 

remove(), element() 와 동일한 동작이다.

 

pollFirst()

덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. 

poll()과 동일한 동작이다.

 

removeLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. 

 

pollLast()

덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. 

 

getFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다.

 

peekFirst()

덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

peek()과 동일한 동작이다.

 

getLast()

덱의 마지막쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다. 

 

peekLast()

덱의 마지막 엘리먼트 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

 

removeFirstOccurrence(Object o)

덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. 

 

removeLastOccurrence(Object o)

덱의 뒤쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. 

 

addAll(Collection <? extends E c)

입력 받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다.

 

push()

addFirst()와 동일. 덱을 스택으로 사용할 때 쓰인다.

 

pop()

removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰인다.

 

remove(Object o)

removeFirstOccurrence(Object o)와 동일하다.

 

contain(Object o)

덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인한다.

 

size()

덱의 크기 

 

iterator()

덱의 앞쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어온다.

 

descendingIterator()

덱의 뒤쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어온다.

 

---

 

 

문제점 : Deque에 대해서 자세히 알지 못했다. 또한, 이전 포스팅에서 댓글로 BufferedReader와 BufferedWriter를 main 밖으로 빼서 main에서는 로직만 확인할 수 있게 되면 좀 더 좋을 것 같다는 피드백을 받았다!

해결 방법 : Deque에 대해 검색하여 메서드를 공부한 뒤 코드를 작성하였다. BufferedReader 와 BufferedWriter를 main 밖에서 정의하도록 하여 코드 가독성을 높였다.

깨달은 바 : 이번 기회에 Deque의 개념에 대해 공부할 수 있었고, 피드백을 받아 발전할 수 있다는 점이 매우 좋았다!!😁