[백준 1158] 요세푸스 문제 (C#, C++) - soo:bak

문제 링크

1158번 - 요세푸스 문제

설명

이 문제는 고전적인 요세푸스 문제를 큐 자료구조로 해결하는 문제입니다.

N명의 사람이 원을 이루고 있고, K번째 사람을 제거하는 과정을 반복하여 제거된 순서대로 출력하는 것이 목적입니다.

---

접근법

• 1부터 N까지의 사람을 큐에 모두 삽입합니다.
• 큐를 순환시키며 K번째 사람을 제거합니다:
  • K-1명은 큐의 뒤로 이동시키고,
  • K번째 사람은 출력 후 제거합니다.
• 모든 사람이 제거될 때까지 반복하고, 출력은 < >로 감쌉니다.

---

Code

[ C# ]

using System;
using System.Collections.Generic;
using System.Text;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      var n = int.Parse(input[0]);
      var k = int.Parse(input[1]);

      var q = new Queue<int>();
      for (int i = 1; i <= n; i++) q.Enqueue(i);

      var sb = new StringBuilder();
      sb.Append('<');
      int cnt = 1;

      while (q.Count > 1) {
        if (cnt % k == 0)
          sb.Append(q.Dequeue()).Append(", ");
        else
          q.Enqueue(q.Dequeue());
        cnt++;
      }
      sb.Append(q.Dequeue()).Append('>');
      Console.WriteLine(sb.ToString());
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;
typedef queue<int> qi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int numP, order; cin >> numP >> order;
  qi circle;

  for (int i = 1; i <= numP; i++) circle.push(i);

  cout << "<";
  int o = 1;
  while (circle.size() > 1) {
    if (o % order == 0) {
      cout << circle.front() << ", ";
      circle.pop();
    }
    else {
      circle.push(circle.front());
      circle.pop();
    }
    o++;
  }
  cout << circle.front() << ">";

  return 0;
}