[큐,덱]#11866 c++ 요세푸스

# 직접 공부하고 통과한 코드입니다.

# 최대한 자세하게 해설 및 풀이 위주로합니다.

# 나름 풀면서 재밌었거나 어려운것들 위주로 올립니다.

 

 

문제를 풀때 가장 첫번째로 해야할건 입력과 출력 예제를 살펴보는 것이다.

7 3이 입력되었고  숫자들이 주룩 나온다.

 

문제를 요약하자면 N명의 사람이 원을 이뤄 앉아 K번째 사람이 빠지는 룰이다.

이는 계속 반복해서 모든 사람이 제거될때까지 반복한다.

 

그림을 그려보자면 이렇다.

예제에 나온 7 3을 기준으로 그려보면

 

중요한건 0에서 3을 더한 3번째 사람이 먼저 제거되지만 카운트 시작은 1로 해야한다는 점이다.

이는 두가지로 해결할 수 있다.

for문으로 반복할 시 0부터 시작해서 3번째마다 제거해라 , 혹은 1부터 시작하되 i==1일때만 +=2 하고 그 외는 +=3해라

 

어느쪽이든 상관없다.

 

STL의 Queue를 사용했는데 1~N까지 들어갈 qData하나와 제거된 사람의 번호를 순서에 따라 넣어줄 용도로 qResult라고 추가해 선언했다.

 

첫번째 for문에서 1부터 N까지 번호를 넣어준 후 qData가 0이 아니면 계속 반복하라고 while문을 써줬고

위에 말한것처럼 난 nCount라는 변수를 만들어 1을 넣어줬다.

 

큐는 인덱스를 통한 접근이 안되고 이터레이터도 없다.

때문에 front 혹은 back을 사용해 해결해야한다.

 

3번째 사람마다 제거해줘야하니 1,2번이 올때는 맨 앞값을 복사해 맨 뒤에 push를 해준 후 pop을 하면

마치 맨 앞값이 맨 뒤로 간것처럼 보인다.

 

3번째가 됐을경우 그냥 pop을 해주면 된다. 이후 nCount를 1로 초기화해 주고 다시 반복을 하면 되는데

3번째마다 pop이 될 경우 qResult에 push를 해서 값을 차례대로 집어넣어주면 된다.

 

#include<iostream>
#include<queue>

int main()
{
	int nInput1{};
	int nInput2{};
	int nCount = 1;
	std::cin >> nInput1 >> nInput2;

	std::queue<int> qData;
	std::queue<int> qResult;

	for (int i = 0; i < nInput1; i++)
	{
		qData.push(i+1);
	}

	while(qData.size() != 0)
	{
		if (nCount == nInput2)
		{
			qResult.push(qData.front());
			qData.pop();
			nCount = 1;
			continue;
		}
		if (qData.size() == 1)
		{
			qResult.push(qData.front());
			break;
		}
		
		qData.push(qData.front());
		qData.pop();
		nCount++;
	}

	int nSize = qResult.size();

	for (int i = 0; i <= nSize; i++)
	{
		if (i == 0)
			std::cout << "<";
		if (i == nSize - 1)
		{
			std::cout << qResult.front() << ">" << std::endl;
			break;
		}
		std::cout << qResult.front() << ", ";
		qResult.pop();
	}
}