ShaShaKa Dev Note

조세퍼스 문제 0

28 June 2019

문제 : https://www.acmicpc.net/problem/11866

이번은 큐의 개념을 익히고 실습하는 문제를 풀어보도록 하겠습니다.

import java.util.Scanner;

public class Main {

    private static Node head = null;

    private static Node tail = null;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        for (int i = 1; i <= N; i++) {
            add(i);
        }

        System.out.print("<");
        while (true) {
            if (head == null) {
                break;
            }
            remove(K);
        }
    }

    private static void add(int data) {
        if (head == null) {
            head = tail = new Node(data);
            head.prev = head;
            head.next = head;
        } else {
            Node node = new Node(data, tail, head);
            head.prev = node;
            tail.next = node;
            tail = node;
        }
    }

    private static void remove(int idx) {

        if (head.prev == head) {
            System.out.print(head.data + ">");
            head = null;
            return;
        }

        Node node = head;
        int count = 1;
        while (count < idx) {
            node = node.next;
            count++;
        }

        System.out.print(node.data + ", ");

        head = node.next;
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
}

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
    }

    Node(int data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

이번에는 큐를 이용해 원순열을 생성하고, 반복적으로 제거하는 문제를 풀어보도록 하겠습니다.
먼저 링크드 노드를 이용해 큐를 생성하고 head와 tail을 지정해줍니다.
head와 tail을 지정하면 새로운 값이 들어왔을 때, head와 tail 사이에만 계속 새로운 노드를 연결해주면 되므로 간편하게 추가가 가능합니다.
이후, 정해진 값에 따라 해당 번째의 노드를 제거해주고 head를 변경해줍니다. 이때부터 head는 다시 제거를 시작하는 기준으로 계속 위치가 변경이 됩니다.
제거를 할 때마다 노드의 data값을 출력해주고, 모든 노드를 제거하면 끝나게 됩니다.