[코딩테스트] BOJ 10866 덱(실패)

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

 

문제

정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

 

출력

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

 

 

예제 입력1

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

 

예제 출력1

2
1
2
0
2
1
-1
0
1
-1
0
3

 

 

예제 입력2

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

 

예제 출력2

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

 

 

풀이

덱을 배열로 구현해서 풀어봤다. 
 

문제

StringBuilder에 출력할 숫자들을 저장해두고 StringBuilder를 ToString()으로 읽어와서 반복문으로 출력했더니 -문자가 출력된다. 
-1이 출력되어야 하는데, -문자가 출력된다. 
 

원인

StringBuilder에 Append로 넣어진 값들은 모두 문자값으로 넣어진다. 
-1을 넣는다면 -라는 문자와 1이라는 문자를 넣는 것이다. 
따라서 StringBuilder를 ToString()으로 문자열로 읽어와서 반복문으로 출력하면 -와 숫자가 따로 출력된다. 
 

해결

StringBuilder말고 StreamWriter를 사용해서 해결했다. 
 
 

내 코드

internal class BOJ10866_덱
{
    public static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    public static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    public static int[] arr;
    public static int head;
    public static int tail;
    public static int size;

    public static void Push_Front(int x)
    {
        arr[--head] = x;
        size++;
    }

    public static void Push_Back(int x)
    {
        //dat[++tail] = x;
        arr[tail++] = x;
        size++;
    }

    public static void Pop_Front()
    {
        if (arr[head] == 0)
            sw.WriteLine(-1);
        else
        {
            sw.WriteLine(arr[head]);
            arr[head] = 0;
            head++;
            size--;
        }
    }

    public static void Pop_Back()
    {
        if (arr[tail - 1] == 0)
            sw.WriteLine(-1);
        else
        {
            sw.WriteLine(arr[tail - 1]);
            arr[tail - 1] = 0;
            tail--;
            size--;
        }
    }

    public static void Front()
    {
        if (arr[head] == 0)
            sw.WriteLine(-1);
        else
            sw.WriteLine(arr[head]);
    }

    public static void Back()
    {
        if (arr[tail - 1] == 0)
            sw.WriteLine(-1);
        else
            sw.WriteLine(arr[tail - 1]);
    }

    public static void Size()
    {
        sw.WriteLine(size);
    }

    public static void Empty()
    {
        if (size > 0)
            sw.WriteLine(0);
        else
            sw.WriteLine(1);
    }

    public static void DequeFunc(string operate, int value)
    {
        switch (operate)
        {
            case "push_front":
                Push_Front(value);
                break;
            case "push_back":
                Push_Back(value);
                break;
        }
    }
    public static void DequeFunc(string operate)
    {
        switch (operate)
        {
            case "front":
                Front();
                break;
            case "back":
                Back();
                break;
            case "size":
                Size();
                break;
            case "empty":
                Empty();
                break;
            case "pop_front":
                Pop_Front();
                break;
            case "pop_back":
                Pop_Back();
                break;
        }
    }

    static void Main(string[] args)
    {
        int N = int.Parse(sr.ReadLine());
        arr = new int[2 * N + 1];
        head = N;
        tail = N;

        string[] inputs;
        string operate = "";
        int value = 0;
        for(int i = 0; i < N; i++)
        {
            inputs = sr.ReadLine().Split(" ");

            operate = inputs[0];

            if(inputs.Length == 2)
            {
                value = int.Parse(inputs[1]);
                DequeFunc(operate, value);
                continue;
            }

            DequeFunc(operate);
        }

        sr.Close();
        sw.Close();
    }
}

 
 

다른 풀이

나는 덱 크기를 push, pop을 할때마다 size변수를 늘려서 계산했었다.
이 풀이는 덱 크기를 tail - head로 풀었다. 이게 더 괜찮은 것 같다. 

internal class BOJ10866_덱
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    const int MX = 1000005;
    static int[] dat = new int[2 * MX + 1];
    static int head = MX;
    static int tail = MX;

    public static void Push_Front(int val)
    {
        dat[--head] = val;
    }

    public static void Push_Back(int val)
    {
        dat[tail++] = val;
    }

    public static void Pop_Front()
    {
        head++;
    }

    public static void Pop_Back()
    {
        tail--;
    }

    public static void Front()
    {
        sw.WriteLine(dat[head]);
    }

    public static void Back()
    {
        sw.WriteLine(dat[tail - 1]);
    }

    static void Main(string[] args)
    {
        int N = int.Parse(sr.ReadLine());

        string[] inputs;
        int val = 0;
        while (N != 0)
        {
            inputs = sr.ReadLine().Split(" ");

            if (inputs[0] == "push_back")
            {
                val = int.Parse(inputs[1]);
                Push_Back(val);
            }
            else if (inputs[0] == "push_front")
            {
                val = int.Parse(inputs[1]);
                Push_Front(val);
            }
            else if(inputs[0] == "pop_front")
            {
                if(tail == head)
                {
                    sw.WriteLine(-1);
                }
                else
                {
                    Front();
                    Pop_Front();
                }
            }
            else if (inputs[0] == "pop_back")
            {
                if(tail == head)
                {
                    sw.WriteLine(-1);
                }
                else
                {
                    Back();
                    Pop_Back();
                }
            }
            else if (inputs[0] == "size")
            {
                sw.WriteLine(tail - head);
            }
            else if (inputs[0] == "empty")
            {
                if(tail == head)
                {
                    sw.WriteLine(1);
                }
                else
                {
                    sw.WriteLine(0);
                }
            }
            else if (inputs[0] == "front")
            {
                if(tail == head)
                {
                    sw.WriteLine(-1);
                }
                else
                {
                    Front();
                }
            }
            else
            {
                if (tail == head)
                {
                    sw.WriteLine(-1);
                }
                else
                {
                    Back();
                }
            }

            N--;
        }

        sr.Close();
        sw.Close();
    }
}