greedy31 [Leetcode] 739. Daily Temperatures 문제 : https://leetcode.com/problems/daily-temperatures/ 일별 온도 정수 배열이 주어지면 해당 날짜에서 볓 번째 날이 지났을 때 해당 날짜의 온도보다 더 높은 온도를 얻을 수 있는지 저장한 배열을 구하라. 만일 가능한 날이 없다면 0을 저장해라. 배열을 뒤에서부터 탐색하면서 stack에 탐색하는 일자의 온도보다 높은 온도만 존재하게 유지한다. 탐색하면서 만일 stack에 탐색 일자의 온도보다 높은 온도가 존재하지 않는다면 0, 존재한다면 stack의 top에 있는 온도의 인덱스에 현재 인덱스를 뺀 값을 정답 배열에 저장한다. Ex) temperatures = [73,74,75,71,69,72,76,73] 시간복잡도는 O(N) 소스코드 C++ : https://gi.. 2021. 11. 13. [LeetCode] 899. Orderly Queue 문제 : https://leetcode.com/problems/orderly-queue/ 문자열 s, 정수 k가 주어진다. 문자열 s의 앞에서부터 k개의 문자들 중 하나를 s문자열의 가장 뒤로 이동시킬 수 있다. 이동횟수와 상관없이 s 문자열의 문자를 이동시켰을 때 얻을 수 있는 문자열들 중 사전순으로 가장 빠른 문자열을 구하라. K가 2이상인 경우, s문자열의 문자들로 만들 수 있는 사전순으로 가장 빠른 문자열이 정답이 될 수 있다. (정렬된 문자열이 정답) 왜냐하면 K가 2이상의 경우 문자들의 개수가 달라지지 않는 한에서 어떤 문자열들도 만들 수 있기 때문이다. 증명해보자. 한 번에 많은 것을 하지 않고 하나의 문자만 올바른 위치로 옮긴다고 생각하면 쉽다. 옮겨야 될 문자를 가장앞에 keep해뒀다가 .. 2021. 9. 5. [codeground] 123. 다이어트 codeground - Practice - SCPC 6회 예선 - 123. 다이어트 문제 : https://www.codeground.org/practice/practiceProblemList 그리디로 풀었다. A 식당, B 식당메뉴들을 오름차순 정렬한다. 가격이 작은 K개의 메뉴들을 가져와서 A 식당 메뉴의 최저가, B 식당 메뉴의 최고가들을 차례로 페어로 묶는다. 페어로 묶은 메뉴 가격들의 합 중 최고가가 정답이 된다. 시간복잡도는 O(NlogN + K). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/123.%20%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8.cpp 2021. 7. 6. [Programmers] 단속카메라 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 그리디로 풀었다. 먼저 루트들을 시작위치를 기준으로 오름차순정렬한다. 변수를 만들어서 커버가능한 시작위치 종료위치(let, cover)를 저장한다. 루트들을 처음부터 탐색하면서 탐색 중인 루트(let, route)가 이전 가능한 카메라 위치로 커버가능한지 체크한다. 만약 route.시작위치 > cover.종료위치 이거나 route.종료위치 < cover.시작위치 라면 범위가 커버가 불가능하므로 카메라를 한 대 더 설치해야한다. 카메라 대수를 한 대 증가시키고 cover 변수를 현재 route 범위로 갱신한다. 이전 카메라로 커버가 가능하다면 현재 route 범위와 cover 범위의 교집합으로 c.. 2021. 6. 16. [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. 이전 1 2 3 4 5 6 다음
