알고리즘 문제408 [Leetcode] 721. Accounts Merge 문제 : https://leetcode.com/problems/accounts-merge/ accounts 2차원 배열이 주어질 때, accounts[i]의 첫번째 요소가 이름이고 나머지는 이메일이다. 두 계정에 공통 이메일이 있는 경우 두 계정을 합쳐라. Union Find 로 풀었다. email을 키 값으로 최근에 email을 가진 유저 이름의 인덱스를 저장한다. 만일 탐색중인 이메일에 이미 인덱스가 저장되어 있다면 union 함수로 현재 탐색하는 account 인덱스와 이메일의 최근 인덱스를 합친다. 동일한 이메일을 가지는 account 인덱스끼리 다 합쳤다면 이후엔 동일 부모를 가지는 account들을 합쳐서 정답 배열을 만들어낸다. 시간복잡도는 O(NM). N = |accounts|, M = |.. 2021. 11. 29. [Leetcode] 242. Valid Anagram 문제 : https://leetcode.com/problems/valid-anagram/ 두 개의 문자열 s, t가 주어질 때, t가 s의 anagram이면 true, 아니면 false를 반환하라. 소문자 알파벳 26개의 횟수를 저장하는 배열을 하나만들어서 s, t를 탐색하며 문자열 s의 문자가이 등장할때는 +1, 문자열 t의 문자가 등장할때는 -1을 해준다. 탐색 후 횟수를 저장한 배열의 모든 요소들이 0인 경우 true, 아닌 경우 false를 반환한다. 시간복잡도는 O(N). N = |s or t| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/242.%20Valid%20Anagram.cpp 2021. 11. 26. [Leetcode] 1375. Bulb Switcher III 문제 : https://leetcode.com/problems/bulb-switcher-iii/ 1 ~ n 까지 번호가 매겨진 n개의 전구가 왼쪽에서 오른쪽으로 나열된 방이 있고, 전구번호를 가진 light 배열이 있다. 모든 전구들은 전구가 꺼져있다. k(0 ~ n-1) 번째에 light[k] 전구를 켠다. 만일 전구가 켜져 있고 해당 전구의 좌측에 있는 모든 전구들 또한 켜져 있다면 전구의 색들이 파란색으로 바뀐다. 켜진 전구들이 모두 파란색이 되는 순간의 횟수를 구해라. k번째에 켜진 모든 전구들이 파란색으로 변경되는 순간은 1 ~ k+1 번째의 전구가 모두 켜져있는 경우밖에 없다. 한 번엔 하나의 전구만 켜지고 전구의 번호는 겹치지 않으므로 이때동안 켜졌던 전구번호중 가장 큰 값이 k+1인 경우가.. 2021. 11. 24. [Leetcode] 952. Largest Component Size by Common Factor 문제 : https://leetcode.com/problems/largest-component-size-by-common-factor/ 고유한 양의 정수 배열 nums가 주어진다. nums[i], nums[j] (i != j)는 1보다 큰 공약수를 공유할 때서로의 노드는 연결되어있다. 그래프에서 가장 큰 연결 컴포넌트의 크기를 구하라. 동일한 약수를 가지는 노드를 연결해야 한다. -> Union-Find 를 사용하자. nums 배열 중 가장 큰 정수를 구한 뒤 그 크기만큼의 부모 배열을 만든다. nums 배열을 차례대로 탐색(let, num)하면서 1보다 큰 약수를 구해야하므로 2부터 탐색중인 정수의 루트까지(let, i) 2중 for 문으로 탐색한다. 만일 num이 i로 나누어떨어진다면 i와 num/i.. 2021. 11. 23. [Leetcode] 289. Game of Life 문제 : https://leetcode.com/problems/game-of-life/ m x n 2차원 배열이 있다. 배열은 1(live) 혹은 0(dead) 로 채워져 있다. 배열의 다음 상태는 각 셀의 8개의 이웃(수직, 수평, 대각선) 의 생사와 관련이 있다. 살아있는 상태의 셀의 살아있는 이웃 수가 2, 3개라면 다음에도 살아있을 수 있다. 하지만 이웃수가 너무적거나(0, 1) 너무 많으면(3초과) 인구과다로 죽게된다. 죽은 상태의 셀의 살아있는 이웃 수가 3개라면 번식한것처럼 되살아난다. 초기 생사 정보를 담은 배열이 입력으로 주어질 때 다음 상태를 반환하라. m x n 배열을 하나 만들어서 모든 셀을 탐색하며 각 셀의 살아있는 이웃들의 수를 저장한다. 다시한번 입력 배열을 탐색하며 만일 살아.. 2021. 11. 23. [Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal 문제 : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 이진 트리의 중위 순회, 후위 순회 결과 배열들이 주어졌을 때 이진 트리를 구하라. 루트노드는 후위순회의 가장 뒤에 있는 노드이다. 후위순회 배열에서 루트 노드를 구한 뒤 중위 순회에서 루트노드의 왼쪽에 있는 값들이 왼쪽 자식 노드들, 오른쪽에 있는 값들이 오른쪽 자식 노드들이 된다. 중위 순회, 후위 순회 배열들의 범위를 위와 같은 방법으로 줄여나가며 재귀함수로 서브트리들의 루트노드, 왼쪽 오른쪽 자식 노드들을 구하며 트리를 만들어나간다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorith.. 2021. 11. 21. 이전 1 ··· 11 12 13 14 15 16 17 ··· 68 다음