문제 풀기 (38) 썸네일형 리스트형 [코딩인터뷰 완전정복] 3.4 스택으로 큐 Q : 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라. #include #include "Stack.h" class MyQueue {private: Stack in; Stack out; bool inputFlag;public: MyQueue() { inputFlag = true; } void push(int n) { if (!inputFlag) { while (out.Size > 0) { in.push(out.pop); } } inputFlag = true; in.push(n); } int pop() { if (inputFlag) { while (in.Size > 0) { out.push(in.pop); } } inputFlag = false; return out.pop(); }};pu.. [코딩인터뷰 완전정복] 3.3 접시 무더기 Q : 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다. ...더보기 #include template class Stack { private: T *start; int nOfE; int size; public: Stack() { start = new T[10]; nOfE = 0; size = 10; } Stack(int N) { start = new T[N]; nOfE = 0; size = N; } void push(T n) { if (nOfE == size) {.. [코딩인터뷰 완전정복] 3.2 스택 Min Q : 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다. #include class stack { private: int *start; int nOfE; int size; int *minStack; int minNofE; int minStackSize; public: stack() { start = new int[10]; nOfE = 0; size = 10; minStack = new int[10]; minNofE = 0; minStackSize = 10; } stack(int N) { start = new int[N]; nOfE = 0; size = N; .. [코딩인터뷰 완전정복] 3.1 한 개로 세 개 Q : 배열 한 개로 스택 3개를 어떻게 구현할지 설명하라. A : 임의접근이 가능하도록 스택을 구현 할 경우 시작 노드가 변하지 않는다. 배열을 3등분해서 각 스택의 공간을 정적으로 할당한다. 공간을 동적으로 사용하려면 스택에 넣을 공간이 부족할 때 스택의 공간을 늘려주고 그자리에 있던 원소들은 밀어준다. 스택을 노드로 구현한다면 공간을 정적으로 지정해 줄 필요없이 세 스택의 총 길이가 배열의 길이를 넘지 않도록만 해준다. [코딩인터뷰 완전정복] 2.8 루프 발견 Q : 순환 연결리스트(circular linked list)가 주어졌을 때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다. ...더보기 // LinkedList.h #include template struct node { T data; node *next; }; template class linked_list{ private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(T n) { node *temp = new node; temp.. [코딩인터뷰 완전정복] 2.7 교집합 Q : 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫 번째 리스트에 있는 k번째 노드와 두 번쨰 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다. A : HashSet을 사용한다. 첫 번째 리스트를 순회하며 각 노드의 주소값을 HashSet에 담는다. 두 번째 리스트를 순회하며 노드의 주소값이 HashSet에 있을 경우 해당 노드부터 End노드 까지의 부분 리스트가 두 리스트의 교집합이다. [코딩인터뷰 완전정복] 2.6 회문 Q : 주어진 연결리스트가 회문(palindrome)인지 검사하는 함수를 작성하라. ...더보기 // LinkedList.h #include template struct node { T data; node *next; }; template class linked_list{ private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(T n) { node *temp = new node; temp->data = n; temp->next = NULL; if (head == NULL) { head = temp; tail = temp; } else { tail->next = temp; tail = tail.. [코딩인터뷰 완전정복] 2.5 리스트의 합 Q : 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라. ...더보기 // LinkedList.h #include struct node { int data; node *next; }; class linked_list { private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(int n) { node *temp = new node; t.. 이전 1 2 3 4 5 다음