[HackerRank] Merge two sorted linked lists / Get Node Value
2021. 7. 19. 16:29
알고리즘
# Merge two sorted linked lists (Linked Lists) [문제] [코드] /* class SinglyLinkedListNode { public: int data; SinglyLinkedListNode *next; SinglyLinkedListNode(int node_data) { this->data = node_data; this->next = nullptr; } }; class SinglyLinkedList { public: SinglyLinkedListNode *head; SinglyLinkedListNode *tail; SinglyLinkedList() { this->head = nullptr; this->tail = nullptr; } void insert_node(i..
[HackerRank] Insert a node at a specific position in a linked list / Compare two linked lists
2021. 7. 19. 14:35
알고리즘
# Insert a node at a specific position in a linked list (Linked Lists) [문제] [코드] SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* llist, int data, int position) { SinglyLinkedListNode *node = new SinglyLinkedListNode(data); if(position == 0) { node->next = llist; llist = node; } int i = 0; SinglyLinkedListNode *temp = llist; while(i != (position-1)) { temp = temp->next; i++; } no..
[HackerRank] Print in Reverse / Delete a Node
2021. 7. 18. 02:56
알고리즘
# Print in Reverse (Linked Lists) [문제] [코드] void reversePrint(SinglyLinkedListNode* llist) { SinglyLinkedListNode *two = NULL, *three, *temp; if(!llist) return; do{ three = two; two = llist; llist = llist->next; two->next = three; } while(llist); for(temp = two; temp; temp = temp->next) cout data next가 three의 값을 가지게 하여 반대로 연결했다. 그리고 llist가 NULL인지 확인하고 해당 과정을 반복하게 된다. llist가 NULL이면 그 다음으로 더이상 노드가..
[HackerRank] Left Rotation / Dynamic Array
2021. 7. 14. 13:57
알고리즘
# Left Rotation (Arrays) [문제] [코드] vector rotateLeft(int d, vector arr) { vector result(arr.size()); int i, j; for(i = 0; i < arr.size(); i++) { j = (i+d) % arr.size(); result[i] = arr[j]; } return result; } [코드설명] 주어진 array를 left rotate 연산하는 문제다. arr내에서 해결하지 않고 추가 배열을 사용해서 해결했다. arr와 동일한 크기의 result 벡터를 만들었다. result 벡터에 arr 벡터의 값을 복사하기 위해 for 반복문으로 벡터의 크기만큼 반복하도록 했다. result의 첫 번째 인덱스부터 값을 채우려고 했..
[HackerRank] Jesse and Cookies / Insertion Sort - Part 1
2021. 7. 9. 03:40
알고리즘
# Jesse and Cookies (Heap) [문제] [코드] void insert_heap(int item, int *heap, int *n) { int i; i = ++(*n); while((i != 1) && item < heap[i/2]) { heap[i] = heap[i/2]; i /= 2; } heap[i] = item; } int delete_heap(int *heap, int *n) { int child, item, temp; item = heap[1]; temp = heap[(*n)--]; child = 2; while(child heap[child+1])) child++; if(temp 1) { result++; num1 = delete_heap(B, &A_count); num2 =..
[HackerRank] QHEAP1 / Quicksort 1 - Partition
2021. 6. 27. 03:38
알고리즘
# QHEAP1 (Heap) [문제] [코드] #include #include #include #include typedef struct { int *arr; int total_node; } Heap; void init_heap(Heap * heap, int n) { heap->arr = (int*)malloc(sizeof(int) * (n + 1)); heap->total_node = 0; } void insert_heap(Heap *heap, int data) { int i; i = ++(heap->total_node); while ((i != 1) && (data arr[i / 2])) { heap->arr[i] = heap->arr[i / 2]; i /= 2; } heap->arr[..
[HackerRank] Tree: Level Order Traversal / Binary Search Tree : Insertion
2021. 6. 26. 12:47
알고리즘
# Tree: Level Order Traversal (Trees) [문제] [코드] struct node* queue[500]; int front = -1, rear = -1; void addq(struct node* node) { queue[++rear] = node; } struct node* deleteq() { return queue[++front]; } void levelOrder(struct node *root) { struct node* temp; if(!root) return; addq(root); while(1) { temp = deleteq(); if(!temp) break; printf("%d ", temp->data); if(temp->left) addq(temp->left); i..
[HankerRank] Tree: Postorder Traversal / Maximum Element
2021. 5. 28. 15:54
알고리즘
# Tree: Postorder Traversal (Trees) [문제] [코드] void postOrder(struct node *root) { if(root) { postOrder(root->left); postOrder(root->right); printf("%d ", root->data); } } [코드설명] 재귀적 호출로 해결했다. 왼쪽 노드와 오른쪽 노드로 순차적으로 내려간 다음, 다시 올라오면서 노드의 data를 출력한다. [채점 결과] # Maximum Element (Stacks) [문제] [코드] int stack[100000]; int top = -1; void push(char *item) { char ch; int val = 0; if (top == 99999) return; fo..
[HackerRank] Tree: Height of a Binary Tree / Tree: Inorder Traversal
2021. 5. 20. 23:14
알고리즘
# Tree: Height of a Binary Tree (Trees) [문제] [코드] int getHeight(struct node* root) { // Write your code here int left, right, height; if(root == NULL) return -1; left = getHeight(root->left); right = getHeight(root->right); height = (left > right ? left : right) + 1; return height; } [코드설명] Divide And Conquer 방식으로 해결했다. 각각 left와 right로 분할해서 각각의 height를 구하고, 두 값을 비교하여 더 큰 값에 1을 더하여 height에 저장한다. ..