본문 바로가기

2019/1212

[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.
[JUnit5] @ParameterizedTest @ParameterizedTest 어노테이션은 테스트 함수에 파라미터로 TC나 결과 등을 주입할 수 있다. // build.gradle.kts dependencies { // add testImplementation("org.junit.jupiter:junit-jupiter-params:5.5.2") } 의존성추가 private fun String?.toIntOrNull(): Int? { return if (this.isNullOrEmpty()) null else try { this.toInt() } catch (e: NumberFormatException) { null } } 테스트를 위와 같은 확장 함수를 하나 만들었다. 문자열이 null이거나 빈 경우 null을 반환하고 아닌 경우 문자열을 Int로.. 2019. 12. 15.
[IntellJ] Kotlin 코드를 java 코드로 확인하기 Tools > Kotlin > Show Kotlin Bytecode 클릭 왼쪽에 있던 코틀린으로 작성했던 Board.kt가 오른쪽과 같이 바이트코드화 되어 결과를 확인할 수 있다. 오른쪽 위에 Decompile 버튼을 누르면 위와 같이 java 코드로 확인할 수 있다. 2019. 12. 9.

티스토리툴바