백준 10866 - 덱

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b10866_%EB%8D%B1.java

 

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

10866번: 덱

일반적인 큐가 한쪽으로 삽입이 가능하고 다른 한쪽으로 빼내는 구조를 가진다면, 덱은 양쪽 방향으로 삽입과 빼내는 것이 다 가능한 구조를 가지고있다.

내가 덱을 구현하는 데에 생각한 알고리즘을 그림으로 그려봤다. 두 개의 스택을 이어붙인 구조를 생각했으며, front와 back을 나타내는 f와 b는 다음에 숫자를 삽입해야할 위치를 나타낸다. 명령의 수 최대가 10000이기 때문에 덱이 최대로 활용될 경우는 push_front를 만번 했을 경우나 push_back을 10000번 했을 경우이기 때문에 덱의 사이즈는 10000+10000 = 20000의 1차원 배열로 만들어주었다. 덱에 숫자가 몇개가 들어있는지는 b-f-1로 구할 수 있었다.

 

import java.io.*;
import java.util.*;
 
public class b10866_덱 {
    public static void main(String args[]) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int f = 9999, b = 10000;  //맨 앞 수의 위치 f와 맨 뒤의 수의 위치 b. 10000과 10001로 잡는다.
        int d[] = new int[20000];  //맨 앞에 임의로 추가한 0번째 배열과 push_front 만번이나 push_back 만번이 배열을 최대로 쓸 경우이므로 10000+10000+1 = 20001 크기의 배열 생성.
        sc.nextLine();
        while (n-- > 0) {
            String s = sc.next();
            if(s.equals("push_front")) {
                int a = sc.nextInt();
                d[f] = a;            
                --f;
            }
            else if(s.equals("push_back")) {
                int a = sc.nextInt();
                d[b] = a;
                ++b;
            }
            else if(s.equals("pop_front")) {
                if(b-f-1 == 0)
                    bw.write("-1\n");
                else {
                    ++f;
                    bw.write(d[f]+"\n");
                }
            }
            else if(s.equals("pop_back")) {
                if(b-f-1==0)
                    bw.write("-1\n");
                else {
                    --b;
                    bw.write(d[b] + "\n");
                }
            }
            else if(s.equals("size")) {
                bw.write(b-f-1+"\n");
            }
            else if(s.equals("empty")) {
                if (b-f-1==0)
                    bw.write("1\n");
                else
                    bw.write("0\n");
            }
            else if(s.equals("front")) {
                if (b-f-1==0)
                    bw.write("-1\n");
                else
                    bw.write(d[f+1]+"\n");
            }
            else if(s.equals("back")) {
                if (b-f-1==0)
                    bw.write("-1\n");
                else
                    bw.write(d[b-1]+"\n");
            }
        }
        bw.flush();
    }
}