1168번 요세푸스 문제 2
이왜틀?
5년 전 메모리 초과
이건 소스 안봐도 알 것 같다.
단순 시뮬레이션으로 접근했다가 메모리 터졌겠지.
StringTokenizer st=new StringTokenizer(br.readLine()," ");
int people=Integer.parseInt(st.nextToken());
int num=Integer.parseInt(st.nextToken());
Queue<Integer> que=new LinkedList<>();
for(int i=1;i<=people;i++){
que.add(i);
}
StringBuilder sb=new StringBuilder();
sb.append("<");
while(!que.isEmpty()){
for(int i=1;i<=num;i++){
if(i!=num){
que.add(que.poll());
}else{
sb.append(que.poll()+(que.isEmpty()?">":", "));
}
}
}
bw.write(sb.toString());
큐를 사용해서 시뮬레이션 했구나
설계
요세푸스 문제의 마지막 생존자를 구하는 건 공식이 있다.
이 문제는 K번째 사람이 사라지는 순서대로 출력을 해야해서 공식을 사용할 수 없다.
머리가 아프지만 세그먼트 트리를 구현하고
K번째 사람을 삭제하며 시뮬레이션해보자.
구현
1. 세그먼트 트리
update 함수 외 현재 살아있는 사람 수와 K번째 제거할 사람을 찾는 함수를 구현한다.
루트노드를 반환하는 getAlive 함수는 현재 원의 크기와 K번째 타겟의 상대적 위치를 구하기 위해 사용하고
K번째 타겟을 반환하는 getDead 함수는 실제 위치를 확인 후 제거하는데 사용한다.
public static class SegmentTree {
int N;
private int size;
private int[] tree;
public SegmentTree(){
this.size = 1;
}
public SegmentTree(int N){
this();
this.N = N;
while(size < N) {
size <<= 1;
}
tree = new int[size * 2];
for (int i = 0 ; i < N ; i++) {
tree[size + i] = 1;
}
for (int i = size - 1 ; i > 0 ; i--) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
public int getAlive() {
// 현재 살아있는 사람 수 == 루트 노드
return this.tree[1];
}
public int getDead(int K) {
int idx = 1;
while (idx < size) {
if(tree[idx * 2] >= K) {
// 왼쪽 노드 생존자 수가 K이상이면 왼쪽으로
idx *= 2;
}else {
// 왼쪽 노드 생존자 수가 K보다 작으면 오른쪽으로
K -= tree[idx * 2];
idx = idx * 2 + 1;
}
}
return idx - size;
}
public void update(int idx, int K) {
int i = size + idx;
tree[i] = K;
// 루트까지 업데이트
while(i > 1) {
i >>= 1;
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
}
2. 시뮬레이션
N명의 사람이 모두 빠져나와야하기 때문에 N번 순회하며
만들어둔 함수로 K번째 타겟의 현재 인덱스를 출력하고 트리에서 제거한다.
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
SegmentTree tree = new SegmentTree(N);
StringBuilder sb = new StringBuilder();
sb.append("<");
int idx = 0;
for (int i = 0 ; i < N ; i++) {
// 살아있는 사람들 중 K번 위치의 사람
idx = (idx + K - 1) % tree.getAlive();
// K번 타겟의 실제 위치
int target = tree.getDead(idx + 1);
if (sb.length() == 1) {
sb.append(target + 1);
}else {
sb.append(", ").append(target + 1);
}
// 타겟 제거
tree.update(target, 0);
}
sb.append(">");
bw.write(sb.toString());
bw.flush();
채점
반성
이제 과거에 틀려서 실패로 남아있는 문제가 30개 아래로 줄어들었다.
문제 하나는 정답률이 0.6%인 번외문제라 제외하고 전부 클리어하는게 목표.
이게 끝이 보이네…
다행히 플래티넘보다 어려운 문제는 없어서 할 수 있을 것 같다.
코드 확인