[백준] no11866: 요세푸스 수열

문제

: N명이 빙 둘러서 앉은 후, 1번부터 시작해 K번째마다 걸리는 사람위치를 출력

N: 사람수

K: 차례

 

링크: https://www.acmicpc.net/problem/11866

---

원리

1. 대기열에 순서대로 세워놓고, 하나씩 꺼내가, 맨 뒤로 보낸다.

2. 그러던 중 K번째로 나온놈은 출력할 문자열에 넣어놓는다.

3. 대기열이 비면 반복을 종료하고 출력한다.

---

풀이방법

1. 데큐(또는 큐) 하나 만든다.

2. 데큐에 N만큼의 숫자를 순차적으로 때려 넣는다.

3. 순차적으로 빼고, 뺀놈은 바로 맨 뒤로 넣는다.

4. K번째가 될 때까지 count를 해주고, K번째가 되면 count는 0으로 다시 된다.

4. K번째 나온 애는 StringBuilder에 넣는다.

5. StringBuilder에 넣을 때, 만약 마지막 숫자가 아니라면, ", "를 추가로 붙여준다.

6. 데큐가 empty되면, 반복을 종료시킨다.

7. StringBuilder에 "<"를 처음 넣어 시작하고, ">"를 마지막에 넣어 출력한다.

 

---

나의 코드

1. String으로 계속 붙여주는 방법 (메모리 21004kB, 시간 188ms)

import java.io.*;
import java.util.*;

public class no11866 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Integer T = Integer.parseInt(st.nextToken());
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=1; i<=T ; i++) dq.add(i);

        Integer num = Integer.valueOf(st.nextToken());
        String result = "<";

        while(!dq.isEmpty()) {
            int count = 1;
            while(num!=count) {
                dq.addLast(dq.pollFirst());
                count++;
            }
            result += dq.pollFirst();
            if(!dq.isEmpty()) result += ", ";
        }
        System.out.println(result+">");
    }
}

 

2. StringBuilder에 넣어서 일괄 출력 (메모리 15840kB, 시간 152ms)

import java.io.*;
import java.util.*;

public class no11866 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Integer T = Integer.parseInt(st.nextToken());
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=1; i<=T ; i++) dq.add(i);

        Integer num = Integer.valueOf(st.nextToken());
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        while(!dq.isEmpty()) {
            int count = 1;
            while(num!=count) {
                dq.addLast(dq.pollFirst());
                count++;
            }
            sb.append(dq.pollFirst());
            if(!dq.isEmpty()) sb.append(", ");
        }
        System.out.println(sb.append(">"));
    }
}

 

---

StringBuilder가 더 빠른 이유

: