Star43 [leetcode][442] Find All Duplicates in an Array 문제 : https://leetcode.com/problems/find-all-duplicates-in-an-array/ 배열크기가 n 일때, 1이상 n이하의 값을 가지는 int형 배열이 주어진다. 배열 요소들은 한 번 혹은 두 번 존재한다. 주어진 배열에서 두 개가 있는 요소들을 구해라. 주목해야 할 점은 배열의 요소들이 1 이상 n 이하라는 점이다. 이를 이용하여 nums배열 값들을 해당 인덱스 위치(nums[i] - 1)에 이동시킬 수 있다. ex) [1,3,4,2] -> [1,2,3,4] 주어진 배열을 앞에서부터 탐색하면서 nums[i] 위치에 i+1 수가 올때까지 다른 요소값과 교환한다. 그러기 위해서는 nums[i]에 있는 수를 nums[i] 인덱스 위치에 있는 수와 swap한다. 예를 들어 .. 2020. 8. 8. [leetcode][621] Task Scheduler 문제 : https://leetcode.com/problems/task-scheduler/ tasks들이 주어질 때 같은 task(같은 알파벳)은 쿨다운 n이 지나기 전까지 실행이 불가능하다고 하자. CPU가 tasks들을 모두 완료하기 위해 걸리는 최소 시간을 구해라. 문제의 핵심은 가장 많이 나온 task가 가장 많은 idle 을 만들 수 있다는 것이다. 따라서 가장 많이 나온 task로 idle 수를 구한 다음 남은 task 들을 idle에 최대한 채워넣는걸 목표로 한다. tasks = { A, A, A, B, B }, n = 2 일 때를 생각해보자. 쿨다운 n은 동일한 task가 가장 많은 수와 관련이 있다. A _ _ A _ _ A 위의 경우 A가 3개, B가 2개 이므로 A만 채웠을 때 idl.. 2020. 8. 1. [leetcode][260] Single Number III 문제 : https://leetcode.com/problems/single-number-iii/ 2개의 요소는 단 하나만 존재하고 이 외의 요소들은 두 개씩 있는 nums 배열이 주어진다. 하나만 존재하는 2개 요소를 찾아라. (요소의 순서는 상관없다. 선형 시간복잡도로 구현하라.) nums 배열을 탐색하면서 모든 요소들의 XOR 연산 결과를 sum 변수에 저장한다. XOR 연산은 홀수번 나온 비트는 1, 짝수번(0포함) 나온 비트는 0으로 세팅된다. 즉, XOR연산 결과는 1개만 존재하는 수의 XOR 결과와 같다. (나머지 수들은 2번 XOR 연산되므로 A XOR A = 0. 이 되므로 무시해도 된다.) 하나만 존재하는 요소를 각각 A, B라고 했을 때, A는 B와 같지 않으므로 A XOR B = 0 .. 2020. 7. 24. [leetcode][15] 3Sum 문제 : https://leetcode.com/problems/3sum/ nums 배열이 주어졌을 때 3개의 수 a,b,c를 nums 배열에서 고를 때 a, b, c의 합이 0이 되는 조합의 수를 구해라. https://withhamit.tistory.com/408 [BOJ][2143] 두 배열의 합 문제 : https://www.acmicpc.net/problem/2143 투 포인터(Two-Pointer)를 이용하여 풀었습니다. 배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1 2020. 7. 8. [BOJ][2143] 두 배열의 합 문제 : https://www.acmicpc.net/problem/2143 투 포인터(Two-Pointer)를 이용하여 풀었습니다. 배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1T) 이므로 R--해줍니다. (L=1 / R=6) 1+5 = 6 (>T) 이므로 R--해줍니다. (L=1 / R=5) 1+4 = 5(==T) 이므로 subA에서 1의 개수 x subB에서 4의 개수를 구하면 2x1 = 2가 됩니다. 곱하는 이유는 부 배열 쌍의 개수를 구하는 것이기 때문입니다. 해당 수를 정답에 더하고 L++, R-- 해줍니다. (L = 1, 2 / R = 4) 2+3 = 5 (==T) 이므로 subA에서 2의 개수(1) x subB에서 3의 개수(1)의 값을 정답에 더하고 L++, .. 2020. 7. 8. [leetcode][96] Unique Binary Search Trees 문제 : https://leetcode.com/problems/unique-binary-search-trees/1..n 의 수로 만들어질 수 있는 BST의 수를 구하라.예시에서 보여주고 있는 n = 3일 때의 만들 수 있는 BST들을 노드 입력 순으로 나열해보자. 1. 1 2 3 2. 1 3 2 3. 2 1 3 (2 3 1) 4. 3 2 1 5. 3 1 2 3번을 보면 [2, 1, 3] 과 [2, 3, 1]의 BST 결과가 같다는 것을 알 수 있다.BST는 루트노드보다 작은 노드들은 루트노드의 왼쪽 서브트리로 가고, 루트노드보다 큰 노드들은 루트노드의 오른쪽 서브트리로 간다.그러므로 2 다음에 1이나올지 3이 나올지는 중요하지 않다는 것이다. 1은 반드시 2의 왼쪽 서브트리로 갈 것이고, 3은 반드시 2.. 2020. 6. 24. 이전 1 ··· 3 4 5 6 7 8 다음
