✅ queue

문제

링크

풀이

1. 문제 접근

N과 K가 주어지고, 1~N 번의 사람이 시계방향으로 순서대로 원을 그리고 있다고 생각하면 1번부터 세어 K번째 사람을 제거하고, 또 그 다음 순번부터 K번째 사람을 제거하는 과정을 반복한다.
이과정에서 제거되는 순번의 순열이 오세푸스 순열이다.

2. 자료구조 선택과 그 이유

1번부터 세어 K번째 사람이 아니면 순번이 넘어가고 K번째 사람은 빼줘야 한다. 순번이 넘어간다는 것은 맨 뒤로 이동한다는 것과 같은 말이다.

즉, queue의 앞 뒤를 이어주면 원과 같은 형태가 된다.

3. 문제 해결 로직 (풀이법)

1번부터 세어 K번째 사람을 셀 때 K번째가 아닌 사람을 pop해서 맨뒤로 push하고 K번째 사람은 pop 해주면 된다.

의사코드

cin >> N >> K

for(i : 1 ~ N){
	que.push(i)
}

while(!que.enpty){
	if(que.front == K){
    	vector.push_back(que.front)
		que.pop
    }
    else{
    	que.push(que.front)
        que.pop
    }
}

print(vector)

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

원 형태로 이동하는 데이터는 큐를 사용하면 된다는 아이디어를 떠올리는 것이 중요한 문제이다.