[백준 C++] 1021, 5430번 회전하는 큐, AC

회전하는 큐

AC

어제에 이어서 이중 연결 리스트로 문제를 풀어봤다. 이제 어느정도 감이 잡혔다. 이중 연결 리스트를 만들 때 head 와 tail 을 꼭 초기화시켜 줘야한다. 그리고 노드끼리 연결이 잘 되어있는지 확인 또 확인해야한다. 마지막으로 head 와 tail 에는 데이터가 저장되어있지 않으면 데이터를 출력할 때 head 와 tail 의 데이터는 출력하지 않도록 주의 해야한다. 

회전하는 큐

코드를 작성하기 전에 어떻게 풀지 생각해놓고 풀었고, 그대로 작성하니 맞았다.

노드가 10 개 있을 경우에는 head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - tail 과 같이 작성했다. 시작할 때 currNode 는 head 이며, currNode 를 기준으로 오른쪽으로 가야 제거해야할 값과 가까운지 왼쪽으로 가야하는지 판단하는 함수(find)를 사용해 가장 적게 2, 3번 함수를 사용하도록 했다. 오른쪽으로 가는 것이 낫다고 판단하면 2번 함수(goNext)를 사용하며, 왼쪽으로 가는 것이 낫다면 1번 함수(goBack)을 사용한다. 목표 노드에 가면 그 노드를 제거하고, 제거한 노드의 다음(next) 노드가 currNode 가 된다. 이 작업을 M 만큼 반복하면 된다.

#include <iostream>
using namespace std;
 
struct Node
{
    int data;
    Node *next;
    Node *prev;
};
 
class List
{
private:
    Node *head;
    Node *tail;
    Node *currNode;
    int size;
    int cnt;
public:
    List(int input);
    int ans;
    bool find(int n);
    void goNext();
    void goBack();
    void remove(int n);
};
 
List::List(int input)  {
  head = new Node;
  tail = new Node;
 
  head -> data = 1;
  head -> prev = tail;
  head -> next = nullptr;
 
  tail -> data = input;
  tail -> prev = nullptr;
  tail -> next = head;
 
  size = input;
  cnt = 0;
  ans = 0;
 
  currNode = head;
 
  for (int i = 2; i <= size - 1; i++) {
    Node *newNode = new Node;
    currNode -> next = newNode;
 
    newNode -> data = i;
    newNode -> prev = currNode;
    newNode -> next = nullptr;
 
    currNode = newNode;
  }
 
  currNode -> next = tail;
  tail -> prev = currNode;
 
  currNode = head;
}
 
bool List::find(int n) {
  Node *tmp = currNode;
  while (tmp -> data != n) {
    tmp = tmp -> next;
    cnt++;
  }
  return (cnt <= (size / 2));
}
 
void List::goNext() {
  currNode = currNode -> next;
  ans++;
}
 
void List::goBack() {
  currNode = currNode -> prev;
  ans++;
}
 
void List::remove(int n) {
  if (find(n)) {
    while(cnt > 0) {
      goNext();
      cnt--;
    }
  } else {
    int tmp = size - cnt;
    while (tmp > 0) {
      goBack();
      tmp--;
    }
    cnt = 0;
  }
  Node *tmp = currNode -> next;
  tmp -> prev = currNode -> prev;
  currNode -> prev -> next = tmp;
  currNode = tmp;
  size--;
}
 
int main()
{
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  int N, M, num;
 
  cin >> N >> M;
 
  List list(N);
  while (M--) {
    cin >> num;
    list.remove(num);
  }
  cout << list.ans << '\n';
  return 0;
}

AC

R 이 나오면 배열을 뒤집고, D 가 나오면 가장 앞에 있는 배열을 제거하는 문제다. 배열에 원소가 없는 상태에서 D 가 나오면 error 를 출력하고, 배열에 원소가 없더라도 D 가 나오지 않으면 빈 배열([])을 출력한다. 문제를 풀 때 실제로 R 이 나올 때마다 뒤집지는 않았고, R 이 나오면 이중 연결 리스트의 탐색 방향을 바꿨다. 예를 들어, direction 의 디폴트 값은 1 인데, direction 이 1일 때 D 가 등장한다면 head 의 next 노드를 삭제한다. 반대로 direction 이 0 인데 D 가 등장한다면 tail 의 prev 노드를 삭제한다. 출력할 때도 direction 이 1 이라면 오른쪽으로 출력하고, 그렇지 않다면 왼쪽으로 출력한다.

#include <iostream>
#include <string.h> // strlen
#include <string> // stoi
using namespace std;
#define DSIZE 100002
#define XSIZE 400003
 
struct Node
{
    int data;
    Node *next;
    Node *prev;
};
 
class List
{
private:
    Node *head;
    Node *tail;
    Node *currNode;
    int size;
    bool direction; // 1 => go Right, 0 => go Left
public:
    List();
    void insert(int ch);
    void remove();
    void initialize();
    void changeDir();
    void print();
};
 
List::List() {
  head = new Node;
  tail = new Node;
  head -> data = 0;
  head -> prev = tail;
  head -> next = tail;
  tail -> data = 0;
  tail -> prev = head;
  tail -> next = head;
 
  currNode = head;
 
  size = 0;
  direction = 1;
}
 
void List::insert(int n) {
  Node *newNode = new Node;
  newNode -> data = n;
  newNode -> prev = currNode;
  newNode -> next = currNode -> next;
  currNode -> next -> prev = newNode;
  currNode -> next = newNode;
  currNode = newNode;
  size++;
}
 
void List::initialize() {
  currNode = head;
}
 
void List::remove() {
  if (direction) {
    Node *tmp = head -> next;
    head -> next = tmp -> next;
    tmp -> next -> prev = head;
    delete tmp;
  } else {
    Node *tmp = tail -> prev;
    tail -> prev = tmp -> prev;
    tmp -> prev -> next = tail;
    delete tmp;
  }
  size--;
}
void List::changeDir() {
  direction = !direction;
}
 
void List::print() {
  Node *tmp = (direction) ? head -> next : tail -> prev;
  int n = size - 1;
  cout << '[';
  if (size != 0) {
    while (1) {
      cout << tmp -> data;
      if (n <= 0) break;
      tmp = (direction) ? tmp -> next : tmp -> prev;
      n--;
      cout << ',';
    }
  }
  cout << ']' << '\n';
}
 
int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  int T, n, cnt = 0;
  char p[DSIZE], arr[XSIZE];
  string str;
 
  cin >> T;
 
  while (T--) {
    cin >> p >> n >> arr;
    cnt = 0;
    for (int i = 0; i < strlen(p); i++) {
      if (p[i] == 'D') cnt++;
    }
 
    if (cnt > n) {
      cout << "error" << '\n';
    } else if (n == 0) {
      cout << "[]" << '\n';
    } else {
      List list;
      int length = strlen(arr);
      for (int i = 1; i < length; i++) {
        if (arr[i] != ',' && arr[i] != ']') str += arr[i];
        else {
          int x = stoi(str);
          list.insert(x);
          str = "";
        }
      }
      list.initialize();
      length = strlen(p);
      for (int i = 0; i < length; i++) {
        if (p[i] == 'R') list.changeDir();
        else list.remove();
      }
      list.print();
    }
  }
  return 0;
}