Medium174 [Leetcode][86] Partition List 문제 : https://leetcode.com/problems/partition-list/ 리스트노드의 head와 정수 x가 주어질 때, x보다 작은 val를 가진 노드들(let, left)은 왼쪽, x와 같거나 큰 val를 가진 노드들(let, right)은 오른쪽으로 정렬된 리스트노드의 헤드를 구하라. 이 때, left, right 그룹 내에서의 노드들은 기존 정렬 순서가 유지되어야 한다. x보다 작은 val 를 가진 노드들을 저장하는 리스트 노드(left)와 x와 같거나 큰 val를 가진 노드들을 저장하는 리스트 노드(right)를 분리시킨다. 만일 left 리스트 노드가 비어있다면 right 리스트 노드의 헤드를 반환한다. left 리스트노드가 비어있지 않다면 left 리스트노드의 마지막 노드의 .. 2021. 4. 14. [Leetcode][17] Letter Combinations of a Phone Number 문제 : leetcode.com/problems/letter-combinations-of-a-phone-number/ 전화 버튼과 동일한 숫자와 문자의 매핑이 있다. 2~9까지의 숫자로 이루어진 문자열이 주어지면 가능한 모든 문자 조합을 반환해라. 하나의 숫자에 복수개의 문자가 매핑되므로 dict[숫자] = 문자의 배열 을 먼저 구해준다. 가능한 문자 조합들은 백트래킹을 이용하여 구한다. 예시로 주어진 23이면 1. 빈 문자열부터 시작해서 2에 해당하는 문자들 중 하나를 넣고("a") 다음 숫자를 판단한다. 2. "a" 이후 3에 해당하는 문자들 중 하나를 세팅한다. "ad". 모든 digits들의 숫자를 판단했으므로 "ad"를 정답에 추가한다. 3. 가장 마지막 문자를 제거한 후('d'가 제거되어 "a.. 2021. 4. 10. [leetcode][870] Advantage Shuffle 문제 : leetcode.com/problems/advantage-shuffle/ 길이가 같은 정수 배열 A, B이 주어질 때, A의 원소의 순서를 변경하여 A[i] > B[i]인 원소의 개수가 최대가 되는 수열 A를 구하여라. 기본 아이디어는 A[i] > B[i] (조건)를 만들 수 있는 A[i] 값은 A 원소가 클수록 조건을 만족할 가능성이 높으며 A 원소가 작을수록 조건을 만족할 가능성이 낮다. 즉, 큰 원소값이 조건을 만족할 수 없으면 이는 작은 원소값도 만족할 수 없다. 따라서 큰 원소값을 세팅할 수 있는 곳에 먼저 세팅하고, 큰 원소값을 사용할 수 없는 곳은 버리는 수로 작은 원소값으로 대체한다. A 배열을 오름차순 정렬하고, B 배열을 {원소값, 인덱스} 배열로 변경하여 이를 오름차순 정렬한.. 2021. 3. 26. [Leetcode][923] 3Sum With Multiplicity 문제 : leetcode.com/problems/3sum-with-multiplicity/ 0이상 100이하의 정수를 가지는 배열 arr이 주어진다. 서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라. 배낭문제로 구할 수 있다. dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수. i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다. num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다. 위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 dp[target][cnt+1] += dp[target-num.. 2021. 3. 23. [Leetcode][823] Binary Trees With Factors 문제 : leetcode.com/problems/binary-trees-with-factors/ 2이상의 정수 배열 arr이 주어진다. arr 배열의 수들을 노드로 가지는 이진트리를 만들고자 한다. 정수들은 중복으로 사용할 수 있고 각 노드들의 값은 자식노드들의 곱과 같다. 조건을 만족하며 만들 수 있는 이진트리의 개수를 구하라. num으로 만들수 있는 서브트리의 수를 메모이제이션으로 캐싱한다. dp[num] = num을 루트로 하는 이진트리의 갯수. dp[num] = dp[num1] x dp[num2] // num1 x num2 = num 점화식은 위와 같다. 따라서, 곱해서 num이 나오는 num1, num2의 세트 배열을 구해야 된다. 2중 for문을 돌려서 arr배열의 요소들을 곱해서 num이 나.. 2021. 3. 14. [Leetcode][581] Shortest Unsorted Continuous Subarray 문제 : leetcode.com/problems/shortest-unsorted-continuous-subarray/ 정수형 배열이 주어질 때, 연속적인 서브배열을 오름차순 정렬하면 전체 배열이 오름차순 정렬이 되게 하는 서브배열의 최소 길이를 구하라. 가장 간단한 방법은 주어진 배열을 오름차순 정렬한뒤 정렬한 배열과 기존 배열을 비교하면서 다른 요소값을 가지는 인덱스의 최소 값과 최대 값을 구한다. 최대값 - 최소값 + 1이 정답이된다. 이 방법으로 한 경우 정렬이 필요하므로 O(NlogN)의 시간이 소요된다. 문제에서는 선형복잡도로 풀 수 있는지 물었으므로 좀 더 효율적인 방법을 살펴보자. [2,6,4,8,10,9,15] 를 예로 들어보자. 배열이 오름차순 정렬이라고 가정한다면, 왼쪽에서 오른쪽으로 .. 2021. 2. 26. 이전 1 ··· 11 12 13 14 15 16 17 ··· 29 다음