본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][334] Increasing Triplet Subsequence 문제 : https://leetcode.com/problems/increasing-triplet-subsequence/ nums 배열이 주어진다. 인덱스 i, j, k (0 one: #2 two = three if three < one: #3 one = three #1 탐색 중인 수(three)가 two보다 큰 경우, one < two < three 인 부분배열이 있다는 뜻이므로 정답이 가능하다. 식은 (one 2020. 1. 2.
[leetcode][46] Permutations 문제 : https://leetcode.com/problems/permutations/ 고유한 정수 모음의 가능한 모든 순열을 구해서 반환하는 문제. 백트래킹으로도 풀 수 있지만 이번에는 반복문으로 풀어보았다. [1, 2, 3] 이 입력으로 주어질때 [] -> [1] -> [1,2] [2,1] -> [1,2,3] [1,3,2] [3,1,2] [2,1,3] [2,3,1] [3,2,1] 위와 같이 배열을 만들어나간다. [1,2] [2,1] -> [1,2,3] [1,3,2] [3,1,2] [2,1,3] [2,3,1] [3,2,1] 을 만드는 과정을 자세히 보면 [1,2] -> [1,2,3] [1,3,2] [3,1,2] / [2,1] -> [2,1,3] [2,3,1] [3,2,1] 이렇게 두가지 리스트 결과를 .. 2019. 12. 23.
[leetcode][719] Find K-th Smallest Pair Distance 문제 : https://leetcode.com/problems/find-k-th-smallest-pair-distance/ 모든 요소들의 pair들의 최소 차 중 k 번째가 되는 수를 구하는 문제. 이진탐색으로 정답이 되는 범위를 줄여나가면서 찾는다. 여기서 low, high, mid는 단순히 nums 배열의 인덱스가 아닌 pair의 차이가 된다. 즉, low = 정답이 가능한 범위의 pair 최소 차이 high = 정답 범위의 pair 최대 차이 mid = 범위를 줄이기 위해 몇 번째 최소 차인지 비교하기 위한 수. 가 된다. nums를 오름차순으로 정렬한다. low = 0, high = 최대값 - 최소값으로 세팅한다. low를 nums를 한 번 탐색하면서 nums[i+1] - nums[i] 중 최소값.. 2019. 12. 21.
[leetcode][140] Word Break II 문제 : https://leetcode.com/problems/word-break-ii/ DFS를 돌리면 TLE가 발생해서 memoization을 추가했다. dp[lastInd] = s[0 ~ lastInd] 로 만들 수 있는 정답 가능 문자열의 리스트이다. 즉 우리가 구할 건 dp[ |str| - 1 ]. 문자열의 뒤에서부터 탐색을 하므로 wordDict의 문자열들의 마지막 문자를 key로 하는 dictionary를 하나 만들었다. ex) wordDict = ["ab", "b", "ac"] -> dict ={ {'b', ["ab", "b"]}, {'c', ["c"]}} dict에서 lastInd를 key로 하는 단어들을 가져온 뒤, 문자열의 서브 문자열이 가능한지 체크한다. ex) banana a가 l.. 2019. 12. 19.
[leetcode][979] Distribute Coins in Binary Tree 문제 : https://leetcode.com/problems/distribute-coins-in-binary-tree/ 루트에서 자식노드로 내려가면서 현재 탐색 중인 노드를 루트로 하는 서브트리의 모든 노드들이 코인을 하나씩 가지고 남는 코인개수를 반환한다. 이 함수를 getCoins라 한다면 수도코드는 다음과 같다. getCoins(root) = getCoins(root.left) + getCoins(root.right) + root.val - 1 root 노드의 val(가지고 있는 코인 개수)와 자식 노드들에게서 남는 코인개수를 가져와서 더해준다. 그리고 1을 빼준다. 이유는 root 노드도 1개의 코인을 가져야하기 때문에 root 몫의 코인 개수(1개)는 제외시켜야 하기 때문이다. 남는 코인개수를.. 2019. 12. 17.
[leetcode][539] Minimum Time Difference 문제 : https://leetcode.com/problems/minimum-time-difference/ 문자열들을 탐색하면서 ':' 기준으로 시, 분을 나눈다. 시 * 60 + 분 (분으로 변환. 정수형)을 리스트에 저장한다. 리스트를 오름차순 정렬한다. 가장 작은 수에 + 24*60 을 리스트의 가장뒤에 추가한다. 리스트를 앞에서부터 탐색하면서 인접한 분들의 차이를 구하고 이들 중 최소값이 정답이 된다. 시간복잡도는 O(NlogN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1266.%20Minimum%20Time%20Visiting%20All%20Points.py 2019. 12. 8.

티스토리툴바