[APS][C++] BOJ G5 28078번 중력 큐

https://www.acmicpc.net/problem/28078

---

문제

(문제는 위 링크에서 확인 부탁드립니다. 이미지와 함께 확인해야 이해가 수월합니다.)

---

풀이

• 큐 뒤에서 삽입 + 공이 나오는 방향은 앞 뒤 모두 가능 ➡️ deque 사용
• 공과 가림막 삽입 방향 주의 ➡️ push_front()와 push_back() 사용 시 주의 (deque의 어느 방향을 뒤로 할건지에 따라 달라질 수 있음)
• 문제에서 입력 종류와 조건이 다양하기 떄문에 조건 정리 시 주의
  • deque의 회전 방향 추적 필요 ➡️ cur_state 변수를 통해 회전 각도로 추적
• 시간 초과를 방지하기 위해 삽입된 공의 개수(count_ball)와 가림막의 개수(count_wall) 추적
  • count 명령이 입력되어 개수를 카운팅하는 경우, 최악의 경우 $ 250,000 \times 250,0000 $ 의 연산 필요

---

코드

#include <deque>
#include <iostream>
#include <string>

using namespace std;

int cur_state = 0;
int count_ball = 0;
int count_wall = 0;

deque<char> dque;

void push_ball() {
  dque.push_front('b');
  count_ball++;
}

void push_wall() {
  dque.push_front('w');
  count_wall++;
}

void pop_que() {
  if (*(--dque.end()) == 'b')
    count_ball--;
  else if (*(--dque.end()) == 'w')
    count_wall--;

  dque.pop_back();
}

void rotate_que(char dir) {
  if (dir == 'l') {
    cur_state = (cur_state - 90 + 360) % 360;
  } else if (dir == 'r') {
    cur_state = (cur_state + 90) % 360;
  }

  return;
}

void count_que(char some) {
  if (some == 'b')
    cout << count_ball << "\n";
  else if (some == 'w')
    cout << count_wall << "\n";
}

void check_state() {
  if (cur_state == 0 || cur_state == 180) return;

  if (cur_state == 90) {
    while (true) {
      if (dque.empty()) return;
      if (dque[dque.size() - 1] == 'w') return;

      dque.pop_back();
      count_ball--;
    }
  }

  if (cur_state == 270) {
    while (true) {
      if (dque.empty()) return;
      if (dque[0] == 'w') return;

      dque.pop_front();
      count_ball--;
    }
  }
}

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

  int Q;
  cin >> Q;

  for (int i = 0; i < Q; i++) {
    string comm;
    cin >> comm;

    if (comm == "push") {
      char temp;
      cin >> temp;

      if (temp == 'b') {
        push_ball();
      } else {
        push_wall();
      }
    } else if (comm == "pop") {
      if (dque.empty()) continue;

      pop_que();
    } else if (comm == "rotate") {
      char temp;
      cin >> temp;

      rotate_que(temp);
    } else if (comm == "count") {
      char temp;
      cin >> temp;

      count_que(temp);
    }

    check_state();
  }

  return 0;
}

---

결과

• 입출력 속도로 인해 시간 초과가 발생할 수 있다. 풀이에서 더 이상 최적화할 방법이 없다는 생각이 든다면, 아래 코드를 main() 함수에 추가하여 입출력 속도를 높여 시간초과를 해결하자. (필자가 테스트하니 아래 코드를 추가하지 않으면 시간초과가 발생하였다.)

...

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  ...
}