본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][435] Non-overlapping Intervals 문제 : https://leetcode.com/problems/non-overlapping-intervals/ interval 배열이 주어질 때 겹치지 않는 interval 요소들을 남기기위해 최소로 삭제해야 하는 interval 수를 구해라. 최소로 삭제해야 한다. = 가장 많은 interval들이 선택(삭제x)되어야한다. 정렬해서 푸는 그리디 문제이다. 끝 지점을 기준으로 오름차순 정렬시킨다. 끝 지점이 같다면 시작지점이 큰 순으로.(많은 interval 들이 선택되어야 하므로 interval이 작은것들먼저 선택되게 한다.) 선택된 interval들의 끝 지점을 last 변수에 저장한다. 정렬된 interval 배열을 앞에서부터 탐색하면서 탐색중인 interval의 시작지점이 last 변수보다 작다면.. 2020. 8. 16.
[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][309] Best Time to Buy and Sell Stock with Cooldown 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 주식가격이 주어질 때 최대 이익을 구하라. 동시에 여러개의 교환은 진행될 수 없다. (즉, 주식을 샀으면 팔때까지 다른 주식을 사고팔수없다.) 주식을 팔았을 때 다음날엔 어떠한 거래도 할 수 없다. (쿨다운 1일) 오랜만에 dfs + dp(memoization). top-down 방식으로 풀었다. dfs(index)를 stock[index~]을 사고 팔 때 얻을 수 있는 최대이익을 가져오는 함수라하자. 이 값은 index에서 어떠한 거래도 하지 않았을 때(dfs(index+1))와 index를 샀을때로 나뉠 수 있다. index 번째 주식을 구입했으면 팔아야 .. 2020. 8. 1.
[leetcode][154] Find Minimum in Rotated Sorted Array II 문제 : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 오름차순 정렬된 배열이 있을 때, 어떤 pivot으로 배열이 회전했다고 하자. ex) [0,1,2,3,4,5,6,7] -> [4,5,6,7,0,1,2,3] 회전된 배열이 주어질 때 가장 작은 수를 구하라. 배열안에 수는 중복될 수 있다. 33번 Search in Rotated Sorted Array 와 비슷하게 풀었다. 위 문제와 다른 점은 33번 문제는 회전된 배열에서 특정 수 target을 찾고 배열은 중복된 수가 없다. 왼쪽 오른쪽 배열 오름차순 오름차순 오름차순 (제일 작은수가 왼쪽에 위치) 오름차순 내림차순 제일 작은수가 오른쪽에 위치 내림차순 오름차순 제일 작.. 2020. 7. 26.
[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.

티스토리툴바