목록자료구조 (26)
어흥
문제 링크: www.hackerrank.com/challenges/two-strings/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Two Strings | HackerRank Given two strings, you find a common substring of non-zero length. www.hackerrank.com 1. 주의할 점 - 문제를 잘 읽자 - KMP 알고리즘을 사용하지 않아도 된다 2. 구현 - 3가지 방법으로 접근했지만 성공한것은 1개 뿐 (1) Set, 시간복잡도: O(N^2*M^2) -> TLE(4/8 성공) - s1의 ..
문제 링크: www.hackerrank.com/challenges/ctci-ransom-note/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Hash Tables: Ransom Note | HackerRank Given two sets of dictionaries, tell if one of them is a subset of the other. www.hackerrank.com 1. 주의할 점 - Map에 대해서 알고있어야 한다 - Magazine에 A 단어가 B개 있을 때, Note에 A 단어가 B개보다 많다면 No 출력 2. 구현 - Magazi..
문제 링크: www.hackerrank.com/challenges/find-the-nearest-clone/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 1. 주의할 점 - BFS를 통해 해결하여 TLE가 나지 않도록 한다 - 방문여부를 기록해둔다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 담는다 - Idx: 현재 Node번호, Val..
문제 링크: www.hackerrank.com/challenges/queue-using-two-stacks/problem?h_r=profile Queue using Two Stacks | HackerRank Create a queue data structure using two stacks. www.hackerrank.com 1. 주의할 점 - Dequeue를 진행할때 마다 여분 스택을 이용하여 스택 전체를 옮기고 빼고 다시 옮기는 일이 없도록 한다 -> TLE 발생 2. 구현 - Enqueue를 수행하는 Stack S, Dequeue에 활용될 Stack os를 사용한다. OS에는 Stack S에 담겨있던 원소들이 역순으로 채워진다 - Front라는 변수를 통해 Queue의 Front에 위치한 수를 저장..
문제 링크: www.hackerrank.com/challenges/maximum-element/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign Maximum Element | HackerRank Given three types of queries, insert an element, delete an element or find the maximum element in a stack. www.hackerrank.com 1. 주의할 점 - 최대값을 어떤 방식으로 저장하고 있을 것인가 - Stack에서 Pop한 이후, Stack이 비었다면 최대값은? 2. 구현 - Info 형태의 구조체를 담는 S..
문제 링크: www.hackerrank.com/challenges/tree-huffman-decoding/problem?h_r=internal-search Tree: Huffman Decoding | HackerRank Given a Huffman tree and an encoded binary string, you have to print the original string. www.hackerrank.com 1. 주의할 점 - 파라미터로 받았던 Tree의 Root를 저장하는 포인터가 있어야 한다 - Leaf에 도달했을 때 처리를 명확히 한다 2. 구현 - Head를 통해 Root 포인터를 기억해놓는다 - 모든 문자를 방문할때까지만 While문을 돌리도록 idx와 len을 통해 조건문을 설정한다 - 파..
문제 링크: www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem Binary Search Tree : Lowest Common Ancestor | HackerRank Given two nodes of a binary search tree, find the lowest common ancestor of these two nodes. www.hackerrank.com 1. 주의할 점 - LCA 정석풀이로 풀 수 있지만, BST의 특성을 활용하면 쉽게 풀 수 있다 - LCA, BST에 대해 알고 있어야 한다 2. 구현 - BST란? 1개의 Node에 최대 2개의 자식이 존재할 수 있다. 또한, 현재 Node를 기준으로 ..
문제 링크: www.hackerrank.com/challenges/binary-search-tree-insertion/problem?h_r=internal-search Binary Search Tree : Insertion | HackerRank Given a number, insert it into it's position in a binary search tree. www.hackerrank.com 1. 주의할 점 - 파라미터로 받은 Root가 NULL이라면? - BST에 새로운 Node(Data)를 추가할 때, 가장 아래에 추가하는데 어떤 방식으로 접근해야 하는가? 2. 구현 - BST에 새로운 Node(Data)를 추가할 때, 가장 아래에 추가하는데 어떤 방식으로 접근해야 하는가?에 대한 대답으로..