https://www.acmicpc.net/problem/11866
문제요약
- 1 부터 주어진 숫자까지의 숫자가 나열
- 다음 주어진 숫자만큼 건너 뛰면서 해당 숫자를 제거하고 출력
이전에 회전하는 큐와 비슷한 문제 접근으로 할 수 있다는 것을 알았다.
왜냐면 3번째 숫자 전까지 옮겨주고, 3번째 숫자를 제거 한뒤 이를 기록하는 방식으로 접근했다면 쉬웠을 것이다.
하지만, 해당 방법은 추후에 생각해 낸 것이고 현재는 규칙을 찾아 시도했다.
1 2 3 4 5 6 7
이라고 가정하면,
1. 오른쪽으로 계속 진행하는 경우, 이경우는 제거 인덱스를 지속적으로 늘려주면된다.
2. 오른쪽에서 다시 처음으로 돌아오는 경우, 이경우의 인덱스를 알아내는 작업이 필요했다.
제거하는 인덱스의 경우, 건너뛰는 크기(step - 1) 씩한 인덱스이다.
지워지는 숫자 |
끝 (지우는 인덱스) +2씩 |
size |
3 |
2 |
7 |
6 |
4 |
6 |
2 |
6 % 5 = 1 ( 여기서 + 2 시작) |
5 |
7 |
3 |
4 |
5 |
5 % 3 = 2 |
3 |
|
4 % 2 = 0 |
2 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
LinkedList<Integer> dq = new LinkedList<>();
String[] row = reader.readLine().split(" ");
int repeat = Integer.parseInt(row[0]);
int step = Integer.parseInt(row[1]);
sb.append("<");
// queue 만들기 1 2 3 4 5 6 7
for (int i = repeat; i >= 1; i--) {
dq.push(i);
}
int tempStep = 0;
// repeat 수만큼 반복
for (int i = 1; i <= repeat; i++) {
if(i == repeat){
sb.append(dq.get(0));
break;
}
tempStep += step - 1;
if(tempStep < dq.size()){
sb.append(dq.get(tempStep) + ", ");
dq.remove(dq.get(tempStep));
} else {
tempStep = tempStep % dq.size();
sb.append(dq.get(tempStep) + ", ");
dq.remove(dq.get(tempStep));
}
}
sb.append(">");
System.out.println(sb);
}
}