그리디2 [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][1200] Minimum Absolute Difference 문제 : https://leetcode.com/problems/minimum-absolute-difference/ arr 배열을 오름차순으로 정렬한다. b - a 값은 오름차순 정렬시 바로 옆에 있는 요소들의 차가 최소 값이 된다. 따라서 정렬된 arr 배열을 앞에서부터 탐색하면서 [arr[i], arr[i-1]]가 [a, b]이다. arr[i-1] - arr[i] 값을 구하고 이 값이 이때동안 계산한 diff의 최소값보다 크다면 정답이 될 수 있으므로 skip. diff 최소 값이랑 같다면 정답배열에 추가. diff 최소 값보다 작다면 이때동안 구한 정답 배열을 빈 배열로 초기화 시키고 정답 배열에 추가한다. 시간복잡도는 정렬하는데 걸리는 시간인 O(NlogN). 소스코드 : https://github.. 2019. 9. 22. 이전 1 다음