1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
1 ~ N 까지 순서대로 저장되어있으면 매번 K번째 수를 제거하고, 제거되는 숫자 순서대로 출력하는 문제입니다.
저는 덱을 이용하여 1 ~ N 까지의 숫자를 넣었고, K번째 수를 제거하기 위해 1 ~ K - 1번째 수를 뒤로 보낸 후에 제거하였습니다.
원래 큐를 이용하는 문제지만 저는 덱이 먼저 떠올라서 덱으로 풀었습니다.
하지만 이유는 모르겠으나 메모리와 시간 차이가 있었습니다.
무슨 이유일까요... 소스 두개모두 올립니다...
아마 ArrayDeque와 LinkedList의 차이인것 같습니다..
LinkedList가 좌 우를 연결하는 link를 다루기때문에 이에대한 추가 메모리 발생과 link 연결을 위한 연산시간이 추가로 발생하는게 아닌가하는 생각이 듭니다.
[Queue]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Queue<Integer> q = new LinkedList<>();
static int N, K;
static void func() {
sb.append("<");
while (!q.isEmpty()) {
for (int i = 0; i < K - 1; i++) {
q.add(q.poll());
}
sb.append(q.poll());
if (!q.isEmpty())
sb.append(", ");
}
sb.append(">");
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++)
q.add(i);
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
[Deque]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Deque<Integer> dq = new ArrayDeque<>();
static int N, K;
static void func() {
sb.append("<");
while (!dq.isEmpty()) {
for (int i = 0; i < K - 1; i++) {
dq.addLast(dq.pollFirst());
}
sb.append(dq.pollFirst());
if (!dq.isEmpty())
sb.append(", ");
}
sb.append(">");
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++)
dq.addLast(i);
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 17299 오등큰수 (0) | 2021.02.22 |
|---|---|
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1918 후위 표기식 (0) | 2021.02.05 |
| boj 1935 후위 표기식2 (0) | 2021.02.05 |
| boj 2493 탑 (0) | 2021.02.04 |