이 포스트는 프로그래밍 문제 풀이 사이트 백준 Online Judge의 덱 구현 문제에 해당하는 10866번 : 덱의 풀이 코드와 해설을 포함하고 있습니다.
또한 이 문제 풀이에서는 구현되어 있는 덱을 사용하지 않고, 기능들을 직접 구현해보는 방식의 풀이를 다룰 것입니다.
10866번 : 덱
문제에서는 덱에 대한 설명 없이 덱을 구현하라고만 되어 있습니다.
덱은 쉽게 말하면 앞뒤로 들어오고 나가는 것이 모두 가능한 비교적 입출력이 자유로운 데이터 구조입니다.
큐와 스택의 성질을 모두 가지고 있다고 생각하면 되며, 대신 두 기능을 모두 구현해야 한다는 점에서 구현이 귀찮을 수는 있습니다.
이 문제에서는 덱의 앞에 넣기, 덱의 뒤에 넣기, 덱의 앞에 있는 수를 빼고 출력하기, 덱의 뒤에 있는 수를 빼고 출력하기, 덱에 들어있는 정수 갯수를 출력하기, 덱이 비어있는지 확인하기, 덱을 빼지 않고 가장 앞에 있는 정수 출력하기, 덱을 빼지않고 가장 뒤에 있는 정수 출력하기의 기능들을 구현하라고 하고 있습니다.
그러면 위의 기능들을 모두 구현해보도록 하겠습니다.
↓ 복사가 가능한 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.
#include <iostream>
#include <string>
using namespace std;
int main() {
int N, D[40000], head = 20000, tail = 20001, digit;
string input;
cin >> N;
for(int i=0; i<N; i++) {
cin >> input;
if(!input.compare("push_front")) {
cin >> digit;
D[head--] = digit;
}
else if(!input.compare("push_back")) {
cin >> digit;
D[tail++] = digit;
}
else if(!input.compare("pop_front")) {
if(head+1 == tail) cout << "-1\n";
else cout << D[++head] << "\n";
}
else if(!input.compare("pop_back")) {
if(head+1 == tail) cout << "-1\n";
else cout << D[--tail] << "\n";
}
else if(!input.compare("size")) cout << tail-head-1 << "\n";
else if(!input.compare("empty")) {
if(head+1 == tail) cout << "1\n";
else cout << "0\n";
}
else if(!input.compare("front")) {
if(head+1 == tail) cout << "-1\n";
else cout << D[head+1] << "\n";
}
else if(!input.compare("back")) {
if(head+1 == tail) cout << "-1\n";
else cout << D[tail-1] << "\n";
}
}
}
구현은 생각보다 아주 쉬운데, 그 이유는 문제에서 데이터와 명령의 수를 작게 제한해주었기 때문입니다.
그렇기 때문에 배열을 크게 선언하고, 중간쯤부터 시작해서 같은 명령이 계속 들어가도 배열의 범위만 벗어나지 않게끔 시작점을 잡아주면 됩니다.
저의 경우에는 배열의 크기를 4만 정도로 잡아서, 2만 정도에서 시작을 하도록 구현하였습니다.
head의 좌표는 20000, tail의 좌표는 20001로 잡고 데이터가 앞으로 들어오면 head를 1 감소시키고 원래의 head 자리에 데이터를 삽입, 데이터가 뒤로 들어오면 tail을 1 증가시키고 원래의 tail 자리에 데이터를 삽입하였습니다.
데이터를 뺄 때도 마찬가지로 head를 증가시키고 그 자리에 있던 데이터를 제거하며, tail을 감소시키고 그 자리에 있던 데이터를 제거하였습니다.
pop front와 front, pop back과 back은 비슷한 기능이고 데이터를 제거하냐 안하냐의 차이이기 때문에 이것은 head와 tail 위치의 변경 유무만 따져서 작성해주면 됩니다.
자세한 기능 구현은 코드를 통해 이해하시면 될 것 같습니다.
제출해보면 생각보다 처리 시간이 오래 걸리면서 정답 처리를 받을 수 있습니다.
이것은 입출력 과정에서의 딜레이 발생일수도 있고, 또는 테스트케이스의 길이를 제한 범위에 꽉꽉 채워서 대입시켜서 그런 것일수도 있지만 아무튼 정답 처리가 되었기 때문에 넘어가도록 하겠습니다.