코딩 테스트 풀이 7 - 요세푸스 문제

✔ 문제

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

💡 첫번째 접근 방법

우선 잦은 삭제가 이루어지므로 LinkedList 또는 CircularQueue를 쓰는 것이 효율적이라고 판단했다. LinkedList 공부중이므로 Node 및 LinkedList를 직접 구현하여 K만큼 현재 노드의 next를 찾고, 그 노드를 지우는 것을 N만큼 반복한다.

⭐ 첫번째 코드

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

class Node
{
    int data;
    Node next;

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

class MyList
{
    Node head;
    MyList(int num)
    {
        // Create head
        head = new Node(1,null);

        // Create Node
        for (int i = 1; i <= num; ++i)
        {
            Node newNode = new Node(i,null);
        }
    }
}

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

        int peopleNum = Integer.parseInt(st.nextToken());
        int josephusNum = Integer.parseInt(st.nextToken());

        MyList myList = new MyList(peopleNum);

        Node curNode = myList.head;
        Node prev = curNode;

        System.out.print("<");
        StringBuilder sb = new StringBuilder();

        for (int i = 0 ; i < peopleNum ;++i)
        {
            for (int j = 0 ; j < josephusNum ; ++j)
            {
                if (curNode.next == null)
                {
                    curNode = myList.head;
                }

                prev = curNode;
                curNode = curNode.next;
            }

            sb.append(curNode.data);

            // remove
            if (curNode == myList.head)
            {
                myList.head = curNode.next;
            }
            else
            {
                prev.next = curNode.next;
            }

            if (i!= peopleNum -1)
            {
                sb.append(", ");
            }
        }

        System.out.print(sb);
        System.out.print(">");
    }
}

💻 다른 방법이 없을까?

코드 통과는 했지만, Java Collection 의 Linked List 를 써서 해보면 어떨까? 라는 생각으로 컬렉션의 LinkedList를 써서 구현했다. 시간도 공간도 이게 더 효율적이다. 다만 의문은, remove 할 때 마치 배열마냥 index를 넣어서 했는데, 이렇게 비효율적이게 말고 다른 방법이 없을까?

⭐ 두번째 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // Receive Input
        int peopleNum = Integer.parseInt(st.nextToken());
        int josephusNum = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder("<");

        LinkedList<Integer> myList = new LinkedList<>();

        // Set element
        for (int i = 1 ; i <= peopleNum ; ++i)
        {
            myList.add(i);
        }

        int currentIndex = 0;

        for (int i = 1 ; i <= peopleNum ; ++i)
        {
            currentIndex = (currentIndex + josephusNum - 1) % (myList.size());
            sb.append(myList.remove(currentIndex ));

            if (i < peopleNum)
            {
                sb.append(", ");
            }
        }

        sb.append(">");
        System.out.print(sb);
    }
}

💻 더 나은 방법이 없을까?

위의 방법보다 더 빠른 방법은 없을까? 저렇게 할바에는 LinkedList가 아니라 ArrayList를 쓰는 것이 더 빠르다. LinkedList를 쓰고, 저것보다 더 빠른 방법을 생각해보자. 첫번째 시도는 Iterator을 사용하는 것이었는데 오히려 시간이 더 많이 걸린다...! 다른 방법을 생각해보자.

⭐ 세번째 코드 continued