백준 10866번 C++ 덱 구현

덱 구현하고 명령어에 따라 출력하기

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

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

문제는 굉장히 간단해 보였다.

가장 오산이었던 건 내가 C++을 야매로 배웠다는 점이었다.

덱 공부하고 한 거기 때문에 출력에는 문제가 없었다.

push_front X와 push_back X 처리가 문제였다...

처음 시도는 char로 받는 거였다. strcmp로 비교하고, str보다 슬라이싱이 번거롭지 않을 것 같았다.

하지만 생각보다 잘 되지 않았다. char*을 또 만들고 어쩌구 저쩌구 하다 보니 시간이 참 잘 갔다.

아무래도 포인터를 쓰다보니 null 문제 때문인지 돌아가지도 않고 진짜 내가 C++을 야매로 하고 있구나 하고 반성했다.

그렇게 뻘짓을 하고 나서 'C++ 문자열 입력받기'에 대해서 검색하던 중 단비같은 글을 발견했다.

string split (https://www.acmicpc.net/board/view/25973)

string split append 같은 걸로 검색하고 있었다. 이때에는 문자열을 공백기준으로 자른 다음 배열에 append하려고 했던 것 같다...

그런데 저 글에서 stringstream이란 것을 알게 되었다.

아무래도 전공 시간에 들은 기억은 있지만... 다시 공부해야겠다.

(stringstream에 대해서는 추후에 추가)

코드

#include <iostream>
#include <sstream>
 
using namespace std;
 
struct node {
    int data;
    node *prev, *next;
 
    static node* getNode(int data) {
        node* new_node = new node();
        new_node->data = data;
        new_node->prev = new_node->next = NULL;
        return new_node; //새로운 노드 추가 시 새로운 노드의 전과 다음은 null
    }
};
 
class deque {
    node* front;
    node* rear;
    int size;
 
public:
    deque() {
        front = rear = NULL;
        size = 0;
    }
 
    void insertFront(int data);
    void insertRear(int data);
    void delFront();
    void delRear();
    int getFront();
    int getRear();
    int getSize();
    void empty();
};
 
void deque::empty() {
    if (front == NULL) {
        cout << 1;
    }
    else {
        cout << 0;
    }
    cout << endl;
}
 
int deque::getSize() {
    return size;
}
 
void deque::insertFront(int data) {
    node* new_node = node::getNode(data);
 
    if (front == NULL) {
        rear = front = new_node;
    }
    else {
        new_node->next = front;
        front->prev = new_node;
        front = new_node;
    }
 
    size++;
}
 
void deque::insertRear(int data) {
    node* new_node = node::getNode(data);
 
    if (rear == NULL) {
        front = rear = new_node;
    }
    else {
        new_node->prev = rear;
        rear->next = new_node;
        rear = new_node;
    }
    size++;
}
 
void deque::delFront() {
    if (front == NULL) {
        cout << -1;
    }
    else {
        cout << front->data;
        node* temp = front;
        front = front->next;
 
        if (front == NULL) {
            rear = NULL;
        }
        else {
            front->prev = NULL;
        }
        free(temp);
        size--;
    }
    cout << endl;
}
 
void deque::delRear() {
    if (front == NULL) {
        cout << -1;
    }
    else {
        cout << rear->data;
 
        node* temp = rear;
        rear = rear->prev;
 
        if (rear == NULL) {
            front = NULL;
        }
        else {
            rear->next = NULL;
        }
        free(temp);
        size--;
    }
    cout << endl;
}
 
int deque::getFront() {
    if (front == NULL) {
        return -1;
    }
    else {
        return front->data;
    }
}
 
int deque::getRear() {
    if (front == NULL) {
        return -1;
    }
    else {
        return rear->data;
    }
}
 
int main() {
    deque dq;
    int N;
 
    cin >> N;
 
    while (N > -1) {
        string str;
        string data;
        stringstream cast;
 
        getline(cin, str);
 
        if (str.find("push_front") == 0) {
            cast << str;
            cast >> data;
            cast >> data;
            str = "push_front";
        }
 
        if (str.find("push_back") == 0) {
            cast << str;
            cast >> data;
            cast >> data;
            str = "push_back";
        }
 
        if (!str.compare("pop_front")) {
            dq.delFront();
        }
        else if (!str.compare("pop_back")) {
            dq.delRear();
        }
        else if (!str.compare("size")) {
            cout << dq.getSize() << endl;
        }
        else if (!str.compare("empty")) {
            dq.empty();
        }
        else if (!str.compare("front")) {
            cout << dq.getFront() << endl;
        }
        else if (!str.compare("back")) {
            cout << dq.getRear() << endl;
        }
        else if (!str.compare("push_front")) {
            dq.insertFront(stoi(data));
        }
        else if(!str.compare("push_back")) {
            dq.insertRear(stoi(data));
        }
 
        N--;
    }
 
    return 0;
}

stoi라는 것도 알게 되었다.

atoi는 알고 있었는데 참으로 편하다. 원래는 string을 char*로 바꿔줬어야 했나 그런데 stoi로 쓰면 string to int로 바로 변환이 된다.

stoi 참고 링크 stackoverflow (https://stackoverflow.com/questions/7663709/how-can-i-convert-a-stdstring-to-int)

결과

이 맛에 푸는 것 같다.

다른 사람에게는 별 거 아닌 문제였을지 몰라도 나는 정말 낑낑대면서 풀었다.

이번 기회에 stringstream과 문자열을 다루는 방법에 대해서 공부했으니... 버린 시간은 아니었다고 생각해야지.

추가

그냥 cin 두 번 쓰면 되는 거였는데...

사실 나도 그렇게 하려고 했는데 cin입력이 스페이스바로 걍 끝나는 건줄 몰랐다 ㅠㅠ

기본적인 것부터 챙겨야겠네