[자료구조] - 코딩인터뷰 스택과 큐

 코딩인터뷰 완전분석에 집필된 문제를 풀이하는 게시글 입니다. 문제공개로 인한 문제가 생길 시 삭제하도록 하겠습니다.

-- 문제

/**************************************************************************************************** 자료구조 03 스택과 큐 2018.11.02 3.1 하나의 배열을 사용해 세 개의 스택을 구현 3.2 push와 pop 두 가지 연산과 함께 최솟값을 반환하는 min을 갖춘 스택을 구현 push, pop, min은 O(1)시간에 처리되도록 구현하시오 3.3 접시 무더기 높이가 특정 수준 이상으로 높아지면 새로운 무더기를 만드는 자료구조 SetOfStacks를 구현 SetOfStacks는 여러 스택으로 구성되어야 하며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. push()와 pop()은 스택이 하나인 경우와 동일하게 동작하도록 구현하시오 3.4 하노이탑 문제  한번에 하나만 옮길 수 있으며 탑의 맨 꼭대기에 있는 원판은 옆에 있는 탑으로 옮길 수 있다.     원판은 자기보다 지름이 큰 원판 위로만 옮길 수 있다. 스택을 사용하여, 첫 번째 탑에 있는 모든 원판을 마지막 탑으로 옮기는 프로그램을 구현하시오. ****************************************************************************************************/

3.1 Solve

 간단한 문제입니다. 조금만 생각하면 풀 수 있는 문제이며 저는 각각의 스택사이즈를 가정하고 배열을 스택사이즈 * 3으로 선언했습니다. 1/3은 1번째 스택, 1/3 ~ 2/3 까지는 2번째 스택 나머지는 3번째 스택으로 나눠서 구현했습니다.

#include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <string> using namespace std; //solve 3.1 -- start const int STACKSIZE = 100; int s[STACKSIZE * 3]; int top[3] = {-1, -1, -1}; //3개의 스택 top포인터 int getTop(int nStack) { return nStack*STACKSIZE + top[nStack]; } void push(int nStack, int value) { top[nStack]++; s[getTop(nStack)] = value; } int pop(int nStack) { int ret = s[getTop(nStack)]; s[getTop(nStack)] = 0; //value 0으로 초기화 top[nStack]--; //top값 1 감소 return ret; }

3.2 Solve

 저는 최솟값을 저장하는 Stack을 하나 더 만들어 구현했습니다. push연산과 pop연산이 이루어질 때 top과 minTop이 동시에 연산이 진행하도록 구현했습니다. 

#include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <string> using namespace std; // solve 3.2 push, pop, min O(1)시간 처리 스택 구현 typedef struct node { int data; struct node* next; } Node; class Stack { private: int cnt; Node* top; Node* minTop; public: Stack(); void push(int); int pop(); int min(); bool isEmpty(); }; Stack::Stack() { cnt=0; top=NULL; }; void Stack::push(int data) { Node *newNode = new Node; newNode->data=data; if(isEmpty()) { top=newNode; minTop=newNode; } else { newNode->next=top; top=newNode; if(newNode->data <= minTop->data) { newNode->next=minTop; minTop=newNode; } } } int Stack::pop() { if(isEmpty()) exit(1); int ret=top->data; if(minTop->data == ret) { minTop=minTop->next; } top=top->next; return ret; } int Stack::min() { return minTop->data; } bool Stack::isEmpty() { if( top == NULL ) return true; else return false; }