[백준 C++] 10866, 1406번 덱, 에디터

덱

에디터

이중 연결리스트를 공부하려고 푼 문제다. 에디터 문제를 먼저 풀었는데 정말이지 죽을 뻔 했다. Node 의 previous Node 와 next Node 를 모두 연결하는 작업이 너무 헷갈리기도 했고, 실수도 많이 할 수 밖에 없는 자료구조인 것 같다. 그래도 에디터 문제를 풀면서 Node 들과 씨름을 하다 보니 좀 익숙해져서 덱 문제는 훨씬 쉽게 풀었다.

덱

덱 문제는 사실 STL 에 있는 것을 가져다와서 사용해도 되는데 처음부터 STL 에 길들여지면 안될 것 같아서 직접 구현하려고 마음먹었다. 이중 연결리스트로 구현할 수있다는 말을 듣고 이중 연결 리스트를 공부해보기로 했다. 

사실 덱을 위한 이중 연결리스트는 중요한 기능이 빠져 있다. 에디터 문제에서도 나오겠지만 이중 연결리스트는 그 이름 답게 연결된 노드들끼리 왔다갔다 하면서 노드들 넣었다가 뺐다가 하는 작업이 복잡한데 여기서는 Front 에 노드를 추가하고 빼며, Back 에 노드를 추가하고 빼는게 전부다.

#include <iostream>
#include <string>
using namespace std;
 
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
class Deque
{
private:
    Node *head;
    Node *tail;
public:
    Deque() {
      head = new Node();
      tail = new Node();
      head -> prev = nullptr;
      head -> next = tail;
      tail -> next = nullptr;
      tail -> prev = head;
    }
    int size = 0;
    void pushFront(int data);
    void pushBack(int data);
    void removeFront();
    void removeBack();
    void front();
    void back();
};
 
void Deque::pushFront(int data) {
  Node *newNode = new Node();
  Node *dummy = head -> next;
 
  newNode -> data = data;
  newNode -> prev = head;
  newNode -> next = dummy;
 
  head -> next = newNode;
  dummy -> prev = newNode;
  size++;
}
 
void Deque::pushBack(int data) {
  Node *newNode = new Node();
  Node *dummy = tail -> prev;
 
  newNode -> data = data;
  newNode -> next = tail;
  newNode -> prev = dummy;
 
  tail -> prev = newNode;
  dummy -> next = newNode;
  size++;
}
 
void Deque::removeFront() {
  if (head -> next != tail) {
    Node *dummy = head -> next;
    cout << dummy -> data << '\n';
    head -> next = dummy -> next;
    dummy -> next -> prev = head;
    delete dummy;
    size--;
  } else cout << -1 << '\n';
}
 
void Deque::removeBack() {
  if (tail -> prev != head) {
    Node *dummy = tail -> prev;
    cout << dummy -> data << '\n';
    tail -> prev = dummy -> prev;
    dummy -> prev -> next = tail;
    delete dummy;
    size--;
  } else cout << -1 << '\n';
}
 
void Deque::front() {
  if (head -> next != tail) {
    cout << head -> next -> data << '\n';
  } else cout << -1 << '\n';
}
 
void Deque::back() {
  if (tail -> prev != head) {
    cout << tail -> prev -> data << '\n';
  } else cout << -1 << '\n';
}
 
int main()
{
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  Deque d;
 
  int TC, n;
  string str;
 
  cin >> TC;
 
  while (TC--) {
    cin >> str;
    if (str == "push_front") {
      cin >> n;
      d.pushFront(n);
    } else if (str == "push_back") {
      cin >> n;
      d.pushBack(n);
    } else if (str == "pop_front") {
      d.removeFront();
    } else if (str == "pop_back") {
      d.removeBack();
    } else if (str == "size") {
      cout << d.size << '\n';
    } else if (str == "empty") {
      cout << ((d.size > 0) ? 0 : 1) << '\n';
    } else if (str == "front") {
      d.front();
    } else if (str == "back") {
      d.back();
    }
  }
  return 0;
}

에디터

정말 힘들게 풀었다. 좀 쉬운 문제를 풀고 다른 문제를 풀어도 되는데 시작부터 너무 어려운 문제를 풀었던 것 같다.

간단한 에디터를 구현하는 문제인데, "abcd"라는 문자가 주어지면 여기서 커서를 옮겨가면서 문자를 넣었다가 빼고 해야한다. 주의할 점은 문자가 n 개면 커서가 놓일 수 있는 곳은 n + 1 가지이다. 문자열 말고도 리스트에 포함된 것이 있는데, head 와 tail 이다. 나는 tail 을 맨 마지막에 놓고, head 를 맨 앞에 놔서 이 문제를 해결했다. head 를 제외한 모든 노드는 자신의 왼쪽에 새로운 노드를 추가할 수 있다. 그래서 "abcd" 와 tail 의 왼쪽에 문자를 넣을 수 있으므로 5개의 위치에 커서를 놓을 수 있다. 

#include <iostream>
#include <string>
using namespace std;
 
struct Node
{
    char data;
    struct Node* next;
    struct Node* prev;
};
 
class List
{
private:
    Node *head;
    Node *tail;
    Node *currNode;
public:
    List() {
      head = new Node();
      tail = new Node();
      head -> prev = nullptr;
      tail -> next = nullptr;
      currNode = tail;
    }
    int cnt = 0;
    void insert(char data);
    void remove();
    void goNext();
    void goBack();
    void print();
};
 
void List::insert(char data) {
  if (cnt == 0) {
    Node *newNode = new Node();
    newNode -> data = data;
    newNode -> next = tail;
    newNode -> prev = head;
    head -> next = newNode;
    tail -> prev = newNode;
  } else {
    Node *newNode = new Node();
    Node *dummy = currNode -> prev;
    newNode -> data = data;
    newNode -> next = currNode;
    newNode -> prev = dummy;
    dummy -> next = newNode;
    currNode -> prev = newNode;
  }
  cnt++;
}
 
void List::remove() {
  if (currNode -> prev != head) {
    Node *dummy = currNode -> prev;
    currNode -> prev = dummy -> prev;
    dummy -> prev -> next = currNode;
    delete dummy;
  }
}
 
void List::goNext() {
  if (currNode -> next != nullptr) currNode = currNode -> next;
}
 
void List::goBack() {
  if (currNode -> prev != head) currNode = currNode -> prev;
}
 
void List::print() {
  Node *tmp = head -> next;
  while (tmp != tail) {
    cout << tmp -> data;
    tmp = tmp -> next;
  }
  cout << '\n';
}
 
int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  List list;
  string str;
  int n;
  char ch;
  cin >> str;
  for (int i = 0; i < str.length(); i++) {
    list.insert(str[i]);
  }
  cin >> n;
  while (n--) {
    cin >> ch;
    if (ch == 'P') {
      cin >> ch;
      list.insert(ch);
    } else if (ch == 'L') {
      list.goBack();
    } else if (ch == 'D') {
      list.goNext();
    } else {
      list.remove();
    }
  }
  list.print();
  return 0;
}