[S5] 11866. 요세푸스 문제 0

https://www.acmicpc.net/submit/11866/45301836

로그인

문제 접근은 쉽게 하였다. 하지만, 내가 푼 방식과 다르게 풀 수 있는 방법이 알고리즘 분류에 소개되어 있어 두 가지의 방법을 소개하려 한다. 

1. 리스트

2. 큐

 

1번부터 알아보자. 리스트로 어떻게?

바로 iterator를 이용하는 것이다.

리스트에 대한 개념이 잡혀있지 않다면 다음 글을 보고 오자.

https://jhcard.tistory.com/14

[C++] List 라이브러리

iterator는 list의 한 요소를 가리키는 포인터라 생각하면 된다.

K만큼 오른쪽으로 이동한다. 이동하는 도중에 l.end()를 만나게 된다면 l.begin()으로 이동하고 K만큼 이동한다. K번째 이동한 후, 그 요소를 erase함수를 사용하여 삭제해준다. 여기에서 erase함수를 사용하여 삭제를 하면 erase함수는 다음을 가리키는 iterator를 반환하게 된다. 그것을 계속해서 유지해준다. 이 행위를 반복하여 리스트가 비워질 때 까지 반복하는 것이다.

#include <cstdio>
#include <list>

int main(void) {
	int N, K; scanf("%d %d", &N, &K);
	std::list<int> l;
	std::list<int>::iterator it;

	for (int i = 1; i <= N; i++) l.push_back(i);
	it = l.begin();
	int turn = 1;
	printf("<");
	while (l.size() != 1) {
		if (turn == K) {
			printf("%d, ", *it);
			it = l.erase(it);
			turn = 1;
		}
		else {
			it++;
			turn++;
		}
		if (it == l.end()) it = l.begin();
	}
	printf("%d>", l.front());
}

 

2. 다음으로 큐 이다. 

개념은 내가 위에서 설명한 내용과 비슷하다.

아. 큐에 대한 이해가 부족하다면 다음 글을 참고하자.

https://jhcard.tistory.com/69

[C++] queue 라이브러리

그러니까 K번 만큼 큐에서 가장 앞에 있는 요소를 맨 뒤로 보내고, K번째가 되면 해당 요소를 출력한 후, 삭제하는 것이다. 그러니까 pop과 front()함수를 이용하여 계속해서 반복해주는 것이다.

#include <cstdio>
#include <queue>

int main(void){
    int N, K; scanf("%d %d", &N, &K);
    std::queue<int> q;
    for(int i = 1; i<= N; i++) q.push(i);
    int turn = 1;
    printf("<");
    while(q.size() != 1){
        if(turn == K){
            printf("%d, ", q.front());
            q.pop();
            turn = 1;
        }
        else{
            turn++;
            q.push(q.front());
            q.pop();
        }
    }
    printf("%d>", q.front());
}

내가 이 글을 작성한 이유는 이러한 종류의 문제를 만나게 된다면 queue를 사용하는 것이 아마 더 효과적일 것이다. 상황에 맞게 큐와 리스트를 구분하여 사용하는 것이 좋다. 참고하도록 하자.