알고리즘 문제/Leetcode283 [leetcode][990] Satisfiability of Equality 문제 : https://leetcode.com/problems/satisfiability-of-equality-equations/ Union-Find로 풀었다.먼저 == 인 경우만 보고 Union-Find로 같아야 하는 알파벳들끼리 그룹으로 묶는다.다음으로 같지 않아야 하는 조건(!=)을 보고 알파벳 두 개의 그룹이 다른지 판단한다. 만약 달라야하는 알파벳 두 개가 서로 같은 그룹이라면 조건이 충돌나므로 false를 반환한다. 소스코드 : https://gist.github.com/fpdjsns/e8e25e4cd52a20322f91556fee3e7994 2019. 2. 11. [leetcode][988] Smallest String Starting From Leaf 문제 : https://leetcode.com/problems/smallest-string-starting-from-leaf/ DFS로 완전탐색해서 풀었다. 루트를 기준으로 자식 노드로 탐색하면서 문자열을 만들어간다.현재 노드의 val를 이때까지 만든 문자열 앞에 붙인다.그리고 리프 노드가 되면 이때까지 만든 문자열을 이때까지 구한 정답 문자열과 비교해서 사전순으로 앞서있다면 정답을 갱신한다. 시간복잡도는 모든 노드를 탐색해야 하므로 O(N + 정답문자열 비교 시간 * 리프노드 개수) 이다.완전이진트리라 했을 때 정답문자열 비교 시간 * 리프노드 개수는 트리의 높이는 logN이므로 정답 문자열 비교 시간은 logN이고 리프노드 개수는 N/2이므로 N*logN/2가 된다.좀 더 상세하게 따지면 몇가지 케이.. 2019. 2. 9. [Leetcode][981] Time Based Key-Value Store 문제 : https://leetcode.com/problems/time-based-key-value-store/ timestamp를 key, value를 value로 하는 map을 하나만들고 이를 value 값으로 가지고 key값을 key로 가지는 unordered_map(정렬될 필요 없으므로)을 만든다.unordered_map m; // {key, {timestamp, value}}cs즉, 위와 같은 맵을 하나 만든다.set할 때에는 key, timestamp, value를 자료형 타입과 맞게 m에 넣어준다. get 할 때는 먼저 key값과 맞는 {timestamp, value}를 찾는다.만약 하나도 없다면 빈 스트링을 반환한다. 맞는 map이 있다면 해당 맵에서 upper_bound를 이용해 time.. 2019. 1. 31. [Leetcode][965] Univalued Binary Tree 문제 : https://leetcode.com/problems/univalued-binary-tree/ TreeNode 포인터(root)와 노드 val를 파라미터로 가지는 재귀함수를 하나 만든다.함수에서는 파라미터로 받은 root 노드가 루트 노드인 서브트리가 정답이 될 수 있는 트리인지 판단하고 그 결과 boolean 값을 반환한다.만약 root 노드가 NULL이거나 root의 val 값이 파라미터로 받은 val과 다르다면 false를 반환한다.그리고 root노드의 왼쪽, 오른쪽 노드를 재귀함수의 파라미터를 가지는 재귀함수를 호출하여 그 결과 값을 받아온다.만약 두 개의 결과 중 하나라도 false라면 false를 반환하고 모두 true라면 true를 반환한다. 소스코드 : https://gist.gi.. 2019. 1. 1. [Leetcode][961] N-Repeated Element in Size 2N Array 문제 : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/ 2N크기의 배열에서 N+1개의 유니크한 값들이 있고 하나만 N번 반복된다.하나의 수가 N번 반복되면 나머지 N개의 수가 남은 배열 크기 N을 채워야 하므로 나머지 수들은 한 번만 나타난다.따라서 2번 이상나오는 수가 정답이 된다.set을 이용해서 구할 수 있다. 소스코드 : https://gist.github.com/fpdjsns/27f0bf48aac4a20315c2f41e8422c663 2018. 12. 23. [Leetcode][954] Array of Doubled Pairs 문제 : https://leetcode.com/problems/array-of-doubled-pairs/ map을 하나 만든다. map의 key는 A 배열의 요소 값이 되고 value는 해당 값이 나온 횟수가 된다. A배열은 절대값 기준으로 오름차순 정렬한다. 문제를 보면 A[i]를 2배 한 값이 있는지만 체크하면 된다. A[i]를 1/2 한 값을 찾거나 *2 한 값을 찾아야 하기 때문에 절대값 오름차순 정렬을 함으로서 *2 한 값만 있는지 체크하기 위함이다. ex) A = {-4, 1, -2} 인 경우 정렬하지 않으면 1/2 (-2)도 체크하고 *2 (-8)한 값도 체크해야 한다. 절대값 기준 오름차순 정렬한다면 A = {1, -2, -4}가 될 것이기 때문에 *2한 값만 체크해도 된다. 값을 찾을 때.. 2018. 12. 21. 이전 1 ··· 40 41 42 43 44 45 46 ··· 48 다음