[자료구조] Java Queue 란? (Queue 메서드 정리, 예제 백준 11866 요세푸스 문제 Java)

[자료구조] Java Queue 란? (Queue 메서드 정리, 예제 백준 11866 요세푸스 문제 Java)

Queue 란?

큐 (Queue) 란 컴퓨터의 기본적인 자료구조 중 한가지 이다.

먼저 집어넣은 데이터가 먼저 나오는 구조이다

First In First Out(FIFO) 구조를 갖고 있다.

즉, 쉽게 생각하면 어떠한 곳을 이용하기 위해 줄을 서는 것과 같다고 생각하면 된다.

먼저 들어온 데이터가 먼저 빠져나가는 방식이다.

한가지 기억나는 재밌는 말이 있다.
햄버거를 주문하러 버거킹에 갔더니 여긴 큐가 3개네? 라고 들었던 말이 생각난다.

Java Queue 사용하기

Java에서는 Queue를 쉽게 사용할 수 있도록 java.util 라이브러리에서 Queue 인터페이스를 지원한다.

Queue를 사용하기 위해서는 import java.util.* 혹은 import java.util.Queue를 사용하면 된다.

인터페이스를 지원한다는 뜻은 직접적으로 생성이 불가능하다는 뜻이고, 그로인해 new LinkedList<>() 를 통하여 생성이 가능하다.

import java.util.Queue;
public class QueueTest{
    public static void main(String[] args){
        Queue<Integer> qInt = new LinkedList<>();

        Queue<Integer> qString = new LinkedList<>();

        Queue<Object> qObject = new LinkedList<>();

    }
}

위와 같은 방법으로 생성이 가능하고, int형, String, Object 등 다양한 타입으로 생성이 가능하다.

Queue Method

오라클 Queue Document

Queue의 메서드는 크게 삽입(Inset), 삭제(Remove), 조회(Examine) 3가지가 존재한다.

각 파트에 두가지씩의 메서드가 존재한다.
하지만, throw Exception을 던지는 경우와, return special value 특별한 return 값을 던지는 경우가 존재하니, 확실히 알고 사용하면 좋을 것 같다.

Method	Contens	return
boolean add(e)	e를 Queue에 삽입	성공 true 반환, 실패 Exception 예외 발생(공간 부족 - IllegalStateException)
boolean offer(e))	e를 Queue에 삽입	성공 true 반환, 실패 false 반환
E remove()	Queue의 헤더 삭제	성공 해당 e 반환, 실패 Exception 예외 발생(Queue가 비었을 경우 - NoSuchElementException )
E poll()	Queue의 헤더 삭제	성공 해당 e반환, 실패 return null
E element()	Queue의 헤더 조회	성공 Queue의 헤더 반환, 실패 Exception 예외 발생(Queue가 비었을 경우 - NoSuchElementException )
E peek()	Queue의 헤더 조회	성공 Queue의 헤더 반환, 실패 return null

백준 11866 요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력

7 3

예제 출력

<3, 6, 2, 7, 5, 1, 4>

Code

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

public class Main{
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i < N + 1; i++){
            q.add(i);
        }

        sb.append("<");

        while(!q.isEmpty()){

            for(int i = 0; i < K - 1; i++){
                q.add(q.poll());
            }
            if(q.size() == 1){
                sb.append(q.poll() + ">");
            } else{
                sb.append(q.poll() + ", ");

            }
        }
        System.out.println(sb);

    }
}

Point

Queue를 이용하기 적합한 문제이다.

처음 이 문제를 보았을 때 Queue를 몰라 배열로만 풀려고 도전했었다.

하지만, Queue를 사용해야된다는 것을 알게되고 공부한 후 조금 빠른 시간내에 풀었다.

매번 K -1번째까지 요소를 삭제해줌과 동시에 Queue의 Tail에 넣어주는 구조이다.
그리고 다음 요소를 삭제하면서 StringBuilder에 넣어줌으로써 출력 구조를 만들었다.