오늘 푼 문제

• 링크: BOJ - 2346 풍선 터트리기
  

문제 요약

이 문제를 간단하게 요약하면 풍선 안에는 숫자가 존재하고, 첫번째 풍선을 터트리며 시작합니다. 첫번째 풍선 안에 있는 숫자로 이동하여 해당 풍선도 터트리고, 해당 풍선 안에 있는 숫자로 이동하며 모든 풍선을 터트릴 때까지 반복하는 것입니다.

문제 풀이

이 문제를 보고 처음에는 풍선을 모두 배열에 저장한 후 해당 풍선의 번호와 인덱스 번호를 일치시켜 이동하며 삭제하는 방식으로 풀이할까 고민했었습니다.

그런데 이렇게 풀면 삭제하는 과정에서 뒤에 있는 값을 모두 앞으로 가져와야 하는 연산을 하게 되는데 그러면 좀 비효율적이다 싶어서 다른 방법이 없나 고민했습니다.

물론 vector를 활용하면 위 과정들을 효과적으로 할 수 있으나 이 역시 직접 해당 풍선으로 위치를 계속 옮기는 과정에서 복잡해질 수 있을것이라 생각했습니다.

그래서 떠올린 방법은 원판 돌리는 것처럼 터트릴 풍선의 번호를 가리키는 것은 고정하고, 풍선을 이에 맞춰 돌리면 쉽게 구현이 되지 않을까 싶었습니다. 회전초밥집 가면 초밥의 위치가 계속해서 바뀌는 것처럼요.

어떤 자료구조가 적합할까 고민하다가 양쪽이 연결되어 자유롭게 이동이 가능한 양방향 연결리스트를 채택했습니다.

그런데 생각해보니 연결리스트는 탐색에 비용이 많이 들어가지만 삽입과 삭제에 있어서는 비용이 적게 들어간다는 장점이 있기 때문에 처음에 떠올린 방법으로 풀어도 되겠다는 생각이 들었습니다.

연결 리스트를 활용한 풀이

#include <iostream>
using namespace std;

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

class DLinkedList {
public:
  Node *head;
  Node *tail;

  DLinkedList() : head(nullptr), tail(nullptr) {}
  void append(int index, int move) {
    Node* newNode = new Node{index, move, nullptr, nullptr};
    if(!head) {
      head = tail = newNode;
      head->next = head;
      head->prev = head;
    } else {
	    // tail 다음에 새로운 노드 추가
	    // 양방향 연결 후 head와 tail도 서로를 가리키며 연결
      newNode->prev = tail;
      newNode->next = head;
      tail->next = newNode;
      head->prev = newNode;
      tail = newNode;
    }
  }

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

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

int main() {
  int n, num;
  cin >> n;

  DLinkedList balloons;

  for(int i = 0; i < n; i++) {
    cin >> num;
    balloons.append(i+1, num);
  }

  Node* cur = balloons.head;
  
  while(!balloons.isEmpty()) {
    int idx = cur->index;
    int move = cur->move;
    cout << idx << " ";

    Node *tmp = cur;
    cur = (move > 0) ? cur->next : cur->prev;
    balloons.erase(tmp);

    if(move > 0) { // 양수면 오른쪽으로 이동
      for(int i = 0; i < move-1; i++) {
        cur = cur->next;
      }
    } else { // 음수면 왼쪽으로 이동
      for(int i = 0; i < -move - 1; i++) {
        cur = cur->prev;
      }
    }
  }

  return 0;
}

그리고 연결리스트 말고 STL를 활용해서도 풀려고 했지만 아직 STL이 아직 손에 익지 않아서 다른 사람의 풀이를 참고했습니다.

Deque을 활용한 풀이

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

int main() {
  deque<pair<int, int>> dq;
  int n, num, cur;
  cin >> n;

  for(int i = 0; i < n; i++) {
    cin >> num;
    dq.push_back(make_pair(num, i+1));
  }

  while(!dq.empty()) {
    cur = dq.front().first;
    cout << dq.front().second << " ";
    dq.pop_front();

    if(dq.empty())
      break;

    if(cur > 0) {
      for(int i = 0; i < cur-1; i++) {
        dq.push_back(dq.front());
        dq.pop_front();
      }
    } else {
      for(int i = 0; i < (-1)*cur; i++) {
        dq.push_front(dq.back());
        dq.pop_back();
      }
    }
  }
}

deque은 알고 있었지만 pair은 몰라서 참고하지 않았다면 해당 STL은 계속 몰랐을 것 같습니다.

pair 사용법은 해당 블로그를 참고했습니다.

마무리

굉장히 오랜만에 알고리즘 문제를 푼 것이라서 풀이도 못 떠올리면 어떡하나 싶었는데 다행히 풀이는 금방 떠올라서 조금은 다행이지 않나 싶었습니다.

그리고 원래 알고리즘은 파이썬을 이용해 풀어서 C++이 아직 미숙하긴 한데 STL이 손에 익기 시작하면 크게 문제 되지는 않을 것 같습니다.