[코딩테스트] BOJ 10845 - 큐 (성공)

 

 

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

 

 

문제

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

명령은 총 여섯 가지이다.

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

예제 출력1

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

 

 

풀이

큐 문제다. 

Collection.Generic에 있는 Queue를 사용해도 되고, 직접 큐를 구현해서 풀어도 되겠다. 

 

큐 구현 풀이

internal class BOJ10845_큐
{
    public const int MAX = 10000;
    public static int[] dataArray = new int[MAX];
    public static int head = 0;
    public static int tail = 0;

    public static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    public static StreamReader sr = new StreamReader(Console.OpenStandardInput());

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

        string[] input;
        int value = 0;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");
            if (input[0] == "push")
            {
                value = int.Parse(input[1]);

                Push(value);
            }
            else if (input[0] == "pop")
            {
                Pop();
            }
            else if(input[0] == "size")
            {
                Size();
            }
            else if(input[0] == "empty")
            {
                Empty();
            }
            else if(input[0] == "front")
            {
                Front();
            }
            else if(input[0] == "back")
            {
                Back();
            }
        }

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

    public static void Push(int value)
    {
        dataArray[tail++] = value;
    }

    public static void Pop()
    {
        if (IsEmpty())
            sw.WriteLine(-1);
        else
            sw.WriteLine(dataArray[head++]);
    }

    public static void Size()
    {
        sw.WriteLine(tail - head);
    }

    public static void Empty()
    {
        if (tail - head == 0)
            sw.WriteLine(1);
        else
            sw.WriteLine(0);
    }

    public static bool IsEmpty()
    {
        if (tail - head == 0)
            return true;
        else
            return false;
    }

    public static void Front()
    {
        if (IsEmpty())
            sw.WriteLine(-1);
        else
            sw.WriteLine(dataArray[head]);
    }

    public static void Back()
    {
        if (IsEmpty())
            sw.WriteLine(-1);
        else
            sw.WriteLine(dataArray[tail - 1]);
    }
}

 

 

Collection.Generic.Stack을 사용한 풀이 

internal class BOJ10845_큐_컬렉션
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        Queue<int> queue = new Queue<int>();

        int N = int.Parse(sr.ReadLine());

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

            if (input[0] == "push")
            {
                value = int.Parse(input[1]);
                queue.Enqueue(value);
            }
            else if(input[0] == "pop")
            {
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                    sw.WriteLine(queue.Dequeue());
            }
            else if(input[0] == "size")
            {
                sw.WriteLine(queue.Count);
            }
            else if(input[0] == "empty")
            {
                if (queue.Count == 0)
                    sw.WriteLine(1);
                else
                    sw.WriteLine(0);
            }
            else if(input[0] == "front")
            {
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                    sw.WriteLine(queue.Peek());
            }
            else if(input[0] == "back")
            {
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                    sw.WriteLine(queue.Last());
            }
        }

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

 

 

복습1 풀이 (6/3)

 

문제 = 정수 저장하는 큐 구현하고, 주어지는 명령 처리하는 프로그램 만들기. 

 

명령

• push X
  • 정수 X를 큐에 넣기.
• pop
  • 큐에 가장 앞 정수 빼고 그 수 출력,
  • 만약 큐 비어있으면 -1 출력
• size
  • 큐에 있는 정수들 개수 출력
• empty
  • 큐 비어있으면 1 출력
  • 큐 비어있지 않으면 0 출력
• front
  • 큐 가장 앞 정수 출력
  • 만약 큐 비어있으면 -1 출력
• back
  • 큐 가장 뒤에 있는 정수 출력
  • 만약 큐 비어있으면 -1 출력 

풀이

큐를 구현하면 된다. 
큐 = 먼저 들어온게 먼저 나가는 자료구조
큐 구성요소
    - front = 큐의 가장 앞 
    - back = 큐의 가장 뒤 

 

 

코드 - 정답

using System.Text;

public class BOJ10845
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    static StringBuilder sb = new StringBuilder();
    
    public static int[] arr = new int[15000];
    public static int front;
    public static int back;
    public static int size;

    static void Main(string[] args)
    {
        int N = int.Parse(sr.ReadLine());
        string[] input;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            switch (input[0])
            {
                case "push":
                    Push(int.Parse(input[1]));
                    break;
                case "front":
                    Front();
                    break;
                case "back":
                    Back();
                    break;
                case "size":
                    Size();
                    break;
                case "empty":
                    Empty();
                    break;
                case "pop":
                    Pop();
                    break;
            }
        }

        sw.WriteLine(sb.ToString());

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

    public static void Push(int number)
    {
        // front는 가만히
        // back은 이동
        arr[back++] = number;
        size++;
    }

    public static void Front()
    {
        if(size <= 0)
            sb.AppendLine("-1");
        else
            sb.AppendLine($"{arr[front]}");
    }

    public static void Back()
    {
        if(size <= 0)
            sb.AppendLine("-1");
        else
            sb.AppendLine($"{arr[back-1]}");
    }

    public static void Size()
    {
        sb.AppendLine($"{size}"); // back - front
    }

    public static void Empty()
    {
        if(size <= 0)
            sb.AppendLine("1");
        else
            sb.AppendLine("0");
    }

    public static void Pop()
    {
        if(size <= 0)
            sb.AppendLine("-1");
        else
        {
            sb.AppendLine($"{arr[front++]}");
            size--;
        }
    }
}