[HackerRank] Cycle Detection
2021. 9. 25. 01:49
알고리즘
# Cycle Detection (Linked Lists) [문제] [코드] bool has_cycle(SinglyLinkedListNode* head) { if(head == NULL) return 0; SinglyLinkedListNode* fast = head; SinglyLinkedListNode* slow = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if(fast == slow) return 1; } return 0; } [코드설명] Linked List에서 cycle의 유무를 확인하는 문제다. 두 개의 포인터를 만들고, 하나는 +1만큼 다른 하나는 +2만큼 링크를 따라..
[HackerRank] Simple Array Sum
2021. 9. 18. 18:45
알고리즘
# Simple Array Sum (Warmup) [문제] [코드] int simpleArraySum(vector ar) { int sum = 0; for(int i = 0; i < ar.size(); i++) sum += ar[i]; return sum; } [코드설명] 배열의 각 요소의 합을 구하는 문제다. 함수의 파라미터로 int형의 vector가 들어왔다. 요소의 합은 int형 변수인 sum에 저장하도록 했다. 본격적으로 합을 구하기에 앞서 값의 오류를 방지하기 위해 sum을 0으로 초기화 했다. 그 후 ar 벡터의 size 메소드로 vector의 크기를 구해 for문의 조건식을 작성하고, sum에 ar벡터의 각 요소를 합했다. for문 종료되면 sum을 반환한다. [채점 결과]
[HackerRank] Sparse Arrays
2021. 9. 18. 18:36
알고리즘
# Sparse Arrays (Arrays) [문제] [코드] vector matchingStrings(vector strings, vector queries) { map m; for (int i = 0; i < queries.size(); i++) m[queries[i]] = 0; for (int i = 0; i < strings.size(); i++) if (m.find(strings[i]) != m.end()) m[strings[i]] += 1; vector result; for (int i = 0; i < queries.size(); i++) result.push_back(m[queries[i]]); return result; } [코드설명] queries 목록에 포함된 단어가 strings 목록..
[HackerRank] Solve Me First
2021. 9. 11. 03:36
알고리즘
# Solve Me First (Warmup) [문제] [코드] int solveMeFirst(int a, int b) { return a+b; } [코드설명] 두 정수의 합을 구하는 문제다. 변수를 따로 생성해서 풀지 않고, a와 b를 더한 값을 바로 반환했다. 이때 a와 b모두 int타입이므로 반환 타입도 int가 된다. [채점 결과]
[HackerRank] Balanced Brackets
2021. 9. 11. 03:30
알고리즘
# Balanced Brackets (Stacks) [문제] [코드] string isBalanced(string s) { stack stack; string result; int i; for(i = 0; i < s.size(); i++) { char c; c = s.at(i); if(c=='(' || c=='{' || c=='[') stack.push(c); else { if(!stack.empty() && ((stack.top()=='(' && c==')') || (stack.top()=='{' && c=='}') || (stack.top()=='[' && c==']'))) stack.pop(); else return "NO"; } } return result = stack.empty() ? "YES..
[HackerRank] Correctness and the Loop Invariant / Running Time of Algorithms
2021. 8. 28. 19:37
알고리즘
# Correctness and the Loop Invariant (Sorting) [문제] [코드] - 원래 코드 void insertionSort(int N, int arr[]) { int i,j; int value; for(i=1;i0 && value
[HackerRank] Binary Search Tree : Lowest Common Ancestor / Insertion Sort - Part 2
2021. 8. 28. 16:45
알고리즘
# Binary Search Tree : Lowest Common Ancestor (Trees) [문제] [코드] Node *lca(Node *root, int v1,int v2) { // Write your code here. int min_v = min(v1, v2); int max_v = max(v1, v2); while(root) { int cur = root->data; // left subtree if (cur > max_v) root = root->left; // right subtree else if (cur right; // LCA else return root; } return root; } [코드설명] LCA(Lowest Common Ancest..
[HackerRank] Inserting a Node Into a Sorted Doubly Linked List / Delete duplicate-value nodes from a sorted linked list
2021. 8. 16. 19:40
알고리즘
# Inserting a Node Into a Sorted Doubly Linked List (Linked Lists) [문제] [코드] DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) { DoublyLinkedListNode *node = new DoublyLinkedListNode(data); DoublyLinkedListNode *temp = llist; DoublyLinkedListNode *prev; if(llist == NULL) return node; if(data data) { node->next = temp; temp->prev = node; llist = node; } else { while(temp =..
[HackerRank] Find Merge Point of Two Lists / Reverse a doubly linked list
2021. 8. 9. 14:56
알고리즘
# Find Merge Point of Two Lists (Linked Lists) [문제] [코드] int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { SinglyLinkedListNode* temp1 = head1, *temp2 = head2; while(temp1 != temp2) { temp1 = (temp1 == NULL) ? head2 : temp1->next; temp2 = (temp2 == NULL) ? head1 : temp2->next; } return temp1->data; } [코드설명] 각 포인터를 동시에 한 단계씩 이동시키면 둘 사이의 간격은 리스트의 크기 차이만큼 난다. 이때 먼저 NULL에..