본문 바로가기
IT/알고리즘(Algorithm)

[JAVA]백준 10845번 문제 풀이

by 공부하는개미 2023. 1. 6.
반응형

# 문제 출제 사이트

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

 

10845번: 큐

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

www.acmicpc.net

 

# 문제

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

명령은 총 여섯 가지이다.

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

 

 

# 입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다.

둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.

문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

# 출력

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

 

 

# 제출한 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            if (command.equals("push")) {
                queue.offer(Integer.parseInt(st.nextToken()));
            } else if (command.equals("pop")) {
                if (queue.isEmpty()) System.out.println("-1");
                else System.out.println(queue.poll());
            } else if (command.equals("size")) {
                System.out.println(queue.size());
            } else if (command.equals("empty")) {
                if (queue.isEmpty()) System.out.println("1");
                else System.out.println("0");
            } else if (command.equals("front")) {
                if (queue.isEmpty()) System.out.println("-1");
                else System.out.println(queue.peek());
            } else if (command.equals("back")) {
                if (queue.isEmpty()) System.out.println("-1");
                else System.out.println(queue.getLast());
            }
        }
    }
}
  • "back" 부분을 해결하기 위해 Deque를 사용해 버렸다.
    => Deque를 사용하지 않고 "back" 조건을 해결해보기로 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            if (command.equals("push")) {
                queue.offer(Integer.parseInt(st.nextToken()));
            } else if (command.equals("pop")) {
                if (queue.isEmpty()) System.out.println("-1");
                else System.out.println(queue.poll());
            } else if (command.equals("size")) {
                System.out.println(queue.size());
            } else if (command.equals("empty")) {
                if (queue.isEmpty()) System.out.println("1");
                else System.out.println("0");
            } else if (command.equals("front")) {
                if (queue.isEmpty()) System.out.println("-1");
                else System.out.println(queue.peek());
            } else if (command.equals("back")) {
                System.out.println(queueBack(queue));
            }
        }
    }

    private static String queueBack(Queue<Integer> queue) {
        if (queue.isEmpty()) { return "-1"; }
        int n = queue.size();
        for (int i = 1; i <= n - 1; i++) {
            queue.add(queue.remove());
        }
        int result = queue.peek();
        queue.add(queue.remove());
        return String.valueOf(result);
    }
}
  • 함수를 따로 만들어서 문제를 해결했다.
  • "back"
    1. queue.isEmpty()가 true이면 "-1"을 리턴한다.
    2. queue의 사이즈의 - 1(n - 1)만큼 반복문을 돌려서 제일 먼저 들어가있는 값들을 다시 넣어준다.
    3."back"에 적합한 숫자가 제일 앞에 와있기 때문에 해당 숫자를 peek() 한다.
    4. "back"에 조건에 부합한 숫자(맨 뒤에 있던 숫자)를 다시 맨 뒤에 넣어준다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        customQueue<Integer> customQueue = new customQueue<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "push":
                    customQueue.push(Integer.parseInt(st.nextToken()));
                    break;

                case "pop":
                    sb.append(customQueue.pop()).append("\n");
                    break;

                case "size":
                    sb.append(customQueue.size()).append("\n");
                    break;

                case "empty":
                    sb.append(customQueue.empty()).append("\n");
                    break;

                case "front":
                    sb.append(customQueue.front()).append("\n");
                    break;

                case "back":
                    sb.append(customQueue.back()).append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}

class customQueue<T> {

    transient  Node<T> first;
    transient  Node<T> last;
    int size = 0;


    public void push(T e) {
        final Node<T> l = last;
        final Node<T> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }

    public String pop() {
        if (size ==0) return "-1";
        final Node<T> f = first;
        final T element = f.item;
        final Node<T> next = f.next;
        f.item = null;
        f.next = null;
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        return element.toString();
    }

    public int size() {
        return size;
    }

    public int empty() {
        if (size == 0) return 1;
        else return 0;
    }

    public T front() {
        if (first == null) return (T) "-1";
        return first.item;
    }

    public T back() {
        if (last == null) return (T) "-1";
        return last.item;
    }


    private class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}
  • LinkedList에 구현되어있는 코드를 참고해서 직접 queue를 구현했습니다.
    queue와 LinkedList의 구조도 배울 수 있고 상당히 도움이 되는 공부였습니다.
    => queue, stack 관련해서 직접 구현하고 블로그에 내용 정리하기(블로그글 링크)

 

 

 

# 참고자료

  • 블로그 <성장하는 코더의 스토리> => 링크
    => 위 블로그가 각 조건에 대해 설명도 잘 나와있다.

 

반응형

관련글

티스토리툴바