BOJ - 1158

1. 문제

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

2. 풀이

문제를 풀고 나서 알고리즘을 확인해보니 큐를 사용하는 문제였다.
근데 큐를 사용한 것보다 나의 풀이가 메모리랑 시간을 덜 잡아먹었다.
원래는 que의 시간복잡도가 더 낮으나 아무래도 로직에서 for문을 돌리는게 원인인듯 하다.

2-1. 내가 한 풀이

import java.util.*;

public class Main1158 {
    public static void main(String [] args){
        Scanner sc  = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N  =sc.nextInt();
        int K = sc.nextInt();
        ArrayList<Integer> numList = new ArrayList<>();
        for(int i = 1; i <=N;i++){
            numList.add(i);
        }
        int count = 1;
        int index = 0;
        sb.append("<");
        while(!numList.isEmpty()){
            if(index >= numList.size())
                index = 0;
            if(count % K == 0){
                int num = numList.get(index);
                sb.append(num).append(", ");
                numList.remove(index);
                index--;
            }
            count++;
            index++;
        }
        sb.delete(sb.length()-1, sb.length());
        sb.delete(sb.length()-1, sb.length());
        sb.append(">");
        System.out.println(sb.toString());
    }
}

2-2. 큐를 활용한 풀이법

import java.util.*;
import java.util.Queue;
public class Main1158 {
    public static void main(String [] args){
        Scanner sc  = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N  =sc.nextInt();
        int K = sc.nextInt();
        Queue<Integer> numQue = new LinkedList<>();
        for(int i = 1; i <=N;i++){
            numQue.add(i);
        }
        int count = 1;
        sb.append("<");
        while(numQue.size() != 1) {
            for (int i = 0; i < K - 1; i++) {
                numQue.offer(numQue.poll());
            }
            sb.append(numQue.poll() + ", ");
        }
        sb.append(numQue.poll() + ">");
        System.out.println(sb.toString());
    }
}

3. 적용된 알고리즘

큐