오늘의 문제

• 링크: BOJ - 1158 요세푸스 문제
  

문제 요약

이번 문제 이전에 풀었던 풍선 터트리기(2346) 문제와 유사합니다. 풍선 터트리기에서는 이동을 풍선에 적힌 숫자로 하였는데, 이 문제에서는 단지 사용자가 입력한 k만큼 이동하는 것이 다른 점입니다.

문제 풀이

풍선 터트리기와 유사하기 때문에 이전과 동일하게 양방향 연결리스트와 덱을 활용하여 풀어봤습니다.

연결리스트를 활용한 풀이

#include <deque>
#include <iostream>
#include <sstream>
using namespace std;

struct Node {
  int index;
  Node *prev;
  Node *next;
};

class DLinkedList {
public:
  Node *head;
  Node *tail;
  DLinkedList() : head(nullptr), tail(nullptr) {}

  void append(int index) {
	  // prev와 next를 tail과 head로 각각 초기화 하여 코드 간략화함.
    Node *newNode = new Node{index, tail, head};
    if (!head) {
      head = tail = newNode;
      head->prev = head->next = head;
    } else {
      tail->next = newNode;
      head->prev = newNode;
      tail = newNode;
    }
  }

  void erase(Node *node) {
    if (node->next == node) {
      delete node;
      head = tail = nullptr;
    } else {
      node->next->prev = node->prev;
      node->prev->next = node->next;
      if (head == node)
        head = node->next;
      if (tail == node)
        tail = node->prev;
      delete node;
    }
  }

  bool isEmpty() { return head == nullptr; }
};

int main() {
  int n, k;
  cin >> n >> k;
  DLinkedList list;

  for (int i = 0; i < n; i++)
    list.append(i + 1);

  Node *cur = list.head;

  cout << "<";
  while (!list.isEmpty()) {
    for (int i = 0; i < k - 1; i++) {
      cur = cur->next;
    }
    cout << cur->index;
    Node *tmp = cur;
    cur = cur->next;
    list.erase(tmp);
    if (!list.isEmpty())
      cout << ", ";
  }
  cout << ">";

  return 0;
}

덱을 활용한 풀이

#include <iostream>
#include <deque>
#include <sstream>
using namespace std;

int main() {
    deque<int> dq;
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        dq.push_back(i + 1);
    }

    stringstream ss;
    ss << "<";

    while(!dq.empty()) {
        for(int i = 0; i < k - 1; i++) {
            dq.push_back(dq.front());
            dq.pop_front();
        }
        ss << dq.front();
        dq.pop_front();
        if (!dq.empty()) {
            ss << ", ";
        }
    }
    ss << ">";

    cout << ss.str() << endl;
    return 0;
}

마무리

이번 문제는 이전에 풀었던 방식을 복기하는 듯한 느낌이 들었습니다. 풀이 과정이 매우 유사하였기 때문입니다.

그렇다고 해서 의미가 없던 것은 아닙니다. 비슷한 문제를 풀어냄으로써 이전 문제를 풀면서 떠올린 풀이들을 머리 속에 더 각인 시킬 수 있었기 때문입니다.