나의 첫 접근
첨부된 이미지
스택을 개별적으로 접근할 수 없기 때문에 이전 스택이 뒤에 추가됩니다.
몇 달 전에 본 사고 방식입니다.
벡터로 해결하는 것은 문제에서 너무 벗어난 것처럼 보였습니다.
다른 사람들의 의견을 확인하십시오.
K 번째 사람 – 순서 관련 변수를 결정하고 K로 나눌 수 있는지 여부를 결정합니다.
K의 배수가 아닌 경우 앞의 요소를 뒤에 추가합니다.
int x = Q.front();
Q.pop(); // 뺄 때는 앞이 빠지고
Q.push(x); // 추가해줄 때는 뒤로 추가가 된다.
무작정 K-1문을 돌려서 쾅 닫았어
대신 K로 나눌 수 있는지 확인하고 조건을 처리하는 것이 조금 더 깔끔해 보입니다.
최종 응답 코드
솔루션 방법:
1. 모든 캐릭터가 제거될 때까지 반복합니다.
2-1 특정 숫자(k)에서 대기열이 팝되고 덤프됩니다.
2-2 특정 순서가 아닌 경우 대기열의 맨 앞에 있는 항목이 맨 뒤로 이동합니다.
3. 다음과 같이 설정합니다.
< > 및 , 가 잘 표시됩니다.
#include <iostream>
#include <queue>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
queue<int> Q;
int N;
int K;
cin >> N >> K;
int removedPerson = 0;
int cur = 1; // 순서
for (int i = 1; i <= N; i++)
{
Q.push(i);
}
cout << "<";
while (removedPerson !
= N) {
while (1) {
if (cur++ % K == 0) {
cout << Q.front(); // 조만간 빼낼 애
Q.pop();
removedPerson++;
break;
}
else {
Q.push(Q.front());
Q.pop();
}
}
if (removedPerson !
= N)cout << ", ";
}
cout << ">";
return 0;
}내에서 생략하려면 break 문을 사용해야하는데 … break 문 사용에 익숙하지 않습니다.
+) 주문이 K의 배수이면 삭제합니다.
+) 제거된 사람 수에 대한 “removedPerson” 변수와 현재 주문에 대한 “current” 변수도 추가했습니다.
크기가 1인지 결정하는 대신 제거된 사람이 N이 될 때까지(removedPerson!
=N) 더 명확해 보입니다.
break 문 없이 시도해 봅시다.
하지만 … 비어 있는지 확인해야합니다
#include <iostream>
#include <queue>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
queue<int> Q;
int N;
int K;
cin >> N >> K;
int removedPerson = 0;
int cur = 1; // 순서
for (int i = 1; i <= N; i++)
{
Q.push(i);
}
cout << "<";
while (removedPerson !
= N) {
while (!
Q.empty()) {
if (cur % K == 0) {
cout << Q.front(); // 조만간 빼낼 애
Q.pop();
removedPerson++;
if (removedPerson !
= N)cout << ", ";
}
else {
Q.push(Q.front());
Q.pop();
}
cur++;
}
}
cout << ">";
return 0;
}Josephus problem #1158) N과 K의 크기만 약간 다를 뿐 나머지는 같습니다.
N과 K는 stl을 사용하지 않으면 5000을 할당해야 합니다.
크기가 5000인 배열 또는 목록과 같습니다.
문제 유형 분석
스택 및 대기열 문제의 경우 프리 프레스 및 버스트가 중요합니다.
어떤 상황에서는 조건을 어떻게 처리하는지, 어떻게 푸시하는지, 어떤 인덱스가 올라가는지가 중요해 보이고, 그게 중요해 보입니다.
오늘 배운 것) 후위 연산자와 break를 사용한 표현 방법: 내 코드와 비교했을 때 확인!