[BOJ-JAVA] 1158번: 요세푸스 문제

문제 해결

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

1158번: 요세푸스 문제

큐를 이용해 쉽게 구현할 수 있는 문제지만, 초기에는 연결리스트만을 사용하여 구현하였고, 이후에 다시 큐를 사용해 구현하였다.

 

연결리스트 사용

• iterator를 사용하여 K번째 마다 remove
• iterator가 끝을 가르킬 때 다시 정의해줘야 하는 번거로움이 있음

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] order = br.readLine().split(" ");
        int N = Integer.valueOf(order[0]);
        int K = Integer.valueOf(order[1]);

        LinkedList<Integer> queue = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            queue.add(i);
        }
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        Iterator iterator = queue.listIterator();
        int count = 1;
        while(!queue.isEmpty()){
            int num = (int)iterator.next();
            if(count == K) {
                sb.append(num).append(", ");
                iterator.remove();
                count = 1;
            }
            else {
                count++;
            }
            if(!iterator.hasNext()){
                iterator = queue.listIterator();
            }
        }
        sb.replace(sb.length()-2, sb.length(), ">");
        System.out.println(sb);
    }
}

 

큐 사용

• 큐는 연결리스트를 사용하여 구현
• K번째가 아니라면 꺼내서 뒤로 보내고, 맞다면 꺼내는 방식
• 코드가 훨씬 간단해짐 

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

public class boj_1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] order = br.readLine().split(" ");
        int N = Integer.valueOf(order[0]);
        int K = Integer.valueOf(order[1]);

        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            queue.offer(i);
        }
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        int count = 1;
        while(queue.size() != 1){
            if(count == K) {
                sb.append(queue.poll()).append(", ");
                count = 1;
            }
            else {
                queue.offer(queue.poll());
                count++;
            }
        }
        sb.append(queue.poll()).append(">");
        System.out.println(sb);
    }
}

 

메모리, 시간 차이

연결리스트

큐

• 큐를 사용했을 때 코드 길이 감소
• 큐를 사용했을 때 시간과 메모리 증가
  • 메모리의 경우 똑같이 linkedlist를 사용하지만 큐는 offer, poll의 반복이기 때문인듯
  • 시간의 경우 연결리스트의 iterator를 사용하면 시간 감소