10845 큐 JAVA

 

요즘 단계별 문제만 풀었더니 실력이 많이 늘지 않는 거 같아 오늘부터 중점적으로 실버 이상의 문제를 풀어보기로 했다.

 

첫 번째 문제는 큐 구현이다. 문제의 조건은 다음과 같다.

 

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

 

큐의 기본 개념에 대해 알고 있는 사람이라면, 위의 명령어들이 큐의 어떤 메서드와 유사한지 바로 눈치를 챌 수 있을 것이다. 한번 API를 살펴보자.

 

 

위의 6 메서드들은 모두 Queue에 정의된 메서드들이다. 하지만 비슷한 기능이 두 쌍이다. 약간 설명을 덧붙이자면

{add(), element(), remove()},   {offer(), peek(), poll()} 이렇게 나눌 수 있다.

 

 

첫 번째 케이스와 두 번째 케이스의 차이점은 간단히 말해서 예외 발생의 차이이다.

 

add()는 저장 공간이 부족할 경우 IllegalStateException이 발생.

remove()와 element() 는 큐가 비어있을 경우 NoSuchElementException 발생

 

반대로 2번째 케이스는 예외 발생 없이 반환타입의 기본값을 반환한다. 

즉, offer()는 추가 실패 시,  false를 반환하고 나머지 두 메서드는 null을 반환한다는 것이다.

 

 

큐에 대한 기본적인 메서드들을 간략히 알아봤으니, 문제로 돌아가서

 

push X : 큐에 X를 넣는 연산이므로, offer()를 이용하여 구현

pop : 큐에 있는 가장 앞에 있는 정수를 제거하고, 출력한다. 만약 비어있다면 -1, poll()을 이용하여 구현

size : 큐의 사이즈를 반환한다. Collection으로부터 상속받은 size()를 이용하여 구현

empty : 큐가 비어있는지 확인, 비어있다면 -1, Collection의 isEmpty()를 이용하여 구현

front : 큐의 가장 앞에 있는 수를 출력한다. (제거 X), peek()을 이용하여 구현

back 큐의 가장 뒤에 있는 수를 출력한다. (제거 X) Deque를 이용하거나, 다른 컬렉션으로 변환

 

 

이렇게 구현할 수 있을 것이다. 일단 여러분도 아시다시피 가장 처음이라는 말은, 가장 먼저 들어온 데이터를 뜻한다.

큐는 기본적으로 FIFO의 구조를 갖고 있기 때문에, 이러한 구현에 유리하다.

 

 

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

public class Q10845 {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Command cd = new Command();
        try {

            int T = Integer.valueOf(br.readLine());

            for(int i = 0; i < T; i++) {
                String input = br.readLine();

                if(input.contains(cd.comList.get(0)))
                    cd.push(input);
                else if(input.contains(cd.comList.get(1)))
                    cd.pop();
                else if(input.contains(cd.comList.get(2)))
                    cd.size();
                else if(input.contains(cd.comList.get(3)))
                    cd.empty();
                else if(input.contains(cd.comList.get(4)))
                    cd.front();
                else if(input.contains(cd.comList.get(5)))
                    cd.back();
            }

        } catch(IOException ioe) {
            ioe.printStackTrace();
        }
    }
}

class Command {
    Queue<Integer> q = new LinkedList();

    List<String> comList =
            new ArrayList<>(List.of("push","pop","size","empty","front","back"));

    public void push(String input) { // 완료
        int num = Integer.valueOf(input.substring(5));
        q.offer(num);
    }

    public void pop() {
        if(q.isEmpty()) {
            System.out.println(-1);
            return;
        }
        int num = q.poll();
        System.out.println(num);
    }

    public void size() {
        System.out.println(q.size());
    }

    public void empty() {
        int num = (q.isEmpty()) ? 1 : 0;
        System.out.println(num);
    }

    public void front() {
        if(q.isEmpty()){
            System.out.println(-1);
            return;
        }
        int num = (q.isEmpty()) ? -1 : q.peek();

        System.out.println(num);
    }

    public void back() {
        ArrayList al = new ArrayList(q);

        if(al.isEmpty()){
            System.out.println(-1);
            return;
        }

        System.out.println(al.get(al.size()-1));
    }
}

 

명령어들을 위와 같이 ArrayList로 보관했지만, 솔직히 ArrayList보단 순서는 중요하지 않고, 중복은 허용하지 않는

Set을 이용한 구현이 더욱 의미가 맞다고 생각했지만, Set은 get()이 없기 때문에 우선은 저렇게 하였다.

 

다른 건 문제의 조건에 따라 조건식을 써서 출력값을 정하면 되는데, 마지막 back()에 대해서만 설명해보려고 한다.

 

우선 Queue는 FiFO의 구조로 마지막에 넣은 데이터를 가져오는 방법은 직접적으론 없는 걸로 알고 있다.

 

이를 위해선 추가 작업이 필요한데, 나는 ArrayList로 새로 만들어서 마지막에 있는 값을 가져오도록 구현하였다.

하지만 이보다도 더 효율적인 방법이 있는데 바로 Deque이다. Deque는 queue와 달리, 앞 뒤로 추가/삭제가 가능하다.

더 자세한 설명은 너무 길어지기에 API를 참고하자.

 

참고로 내가 할 수 있는 한 효율적으로 짠 코드는 큐2에 정리해두었다.