# 직접 공부하고 통과한 코드입니다.
# 최대한 자세하게 해설 및 풀이 위주로합니다.
# 나름 풀면서 재밌었거나 어려운것들 위주로 올립니다.
문제를 풀때 가장 첫번째로 해야할건 입력과 출력 예제를 살펴보는 것이다.
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();
}
}
'# 공부 > # 알고리즘' 카테고리의 다른 글
Dynamic Programming [ 동적 계획법 ] (0) | 2021.11.09 |
---|---|
#2146 c++ 백준 알고리즘 간단한 설명 및 코드 (0) | 2021.04.06 |
[스택] 괄호 :: 백준 알고리즘 9012번 C++ (0) | 2021.01.17 |
[스택] 제로 :: 백준알고리즘 10773번 c++ (0) | 2021.01.17 |
[스택] 백준알고리즘 10828번 c++ (0) | 2021.01.17 |