본문 바로가기
반응형

greedy18

[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.
[leetcode][1029] Two City Scheduling 문제 : https://leetcode.com/problems/two-city-scheduling/ 2N명을 도시 A, B에 각각 N명씩 이동시키려고 한다. 각각 A, B로 이동시키는 비용이 주어질 때 이동시키는 비용의 최소값을 구해라. A아니면 B로 이동시킨다. -> 둘 중 하나는 선택되어야 한다. 하나는 선택되어야 하므로 한 명의 A, B 이동 비용을 비교해야 되고 두 방법 중 이동 비용이 작은쪽으로 이동시켜야 이득이다. 각자 A로 이동시키는 비용 - B로 이동시키는 비용을 구해서 오름차순으로 정렬한다. (B가 A보다 크거나, A비용이 더 크지만 B와의 비용 차이가 별로 나지 않을 수록 앞에 정렬된다.) 앞에서부터 N명은 A로, 그 뒤 N명은 B로 이동시킨다. 시간복잡도는 O(NlogN). 소스코드 .. 2020. 6. 4.
반응형