본문 바로가기

전체 글657

[leetcode][42] Trapping Rain Water 문제 : https://leetcode.com/problems/trapping-rain-water/ 땅의 고도를 나타내는 배열이 주어질 때, 비가 내린 후 가둘 수 있는 물의 양을 구해라. 예시로 주어진 [0,1,0,2,1,0,1,3,2,1,2,1] 을 한 번 살펴보자. 예시의 5 인덱스를 보면 가둘 수 있는 물의 양은 양 옆에 있는 고도가 아닌 인덱스 5를 기점으로 왼쪽에 있는 고도 중 가장 높은 것(leftMax)과 오른쪽에 있는 고도 중 가장 높은 것(rightMax)이 관계가 있다. leftMax와 rightMax를 구했다면 이들 중 더 낮은 고도 - 탐색 중인 고도가 가둘 수 있는 물의 양이다. 인덱스 5를 예로 들면 leftMax = 2(index 3). rightMax = 3(index 7).. 2020. 8. 22.
[테트리스] 19. 블록 회전 개선 (1) 오늘의 이슈. 올게 왔군. 현재 블럭은 4x4 배열이다. 회전시 왼쪽, 시계반대방향으로 블럭이 회전시키자. 1 (0,0) 2 (0,1) 3 (0,2) 4 (0,3) 5 (1,0) 6 (1,1) 7 (1,2) 8 (1,3) 9 (2,0) 10 (2,1) 11 (2,2) 12 (2,3) 13 (3,0) 14 (3,1) 15 (3,2) 16 (3,3) 배열로 표현하면 위와 같은 걸 회전하면 4 (0,0) 8 (0,1) 12 (0,2) 16 (0,3) 3 (1,0) 7 (1,1) 11 (1,2) 15 (1,3) 2 (2,0) 6 (2,1) 10 (2,2) 14 (2,3) 1 (3,0) 5 (3,1) 9 (3,2) 13 (3,3) 위 배열로 바껴야한다. (x, y) -> (size - y, x) 로 변경되는 것을.. 2020. 8. 17.
[leetcode][295] Find Median from Data Stream 문제 : https://leetcode.com/problems/find-median-from-data-stream/ 정렬된 배열의 중앙값을 찾아라. 만약 배열에 짝수개 있다면 중앙값 2개의 평균값을 구해라. addNum(num) num을 배열에 추가한다. findMedian() 배열의 중앙값을 구하라. 최소힙, 최대힙 으로 푸는 유명한 문제. 왼쪽에는 최대힙, 오른쪽에는 최소힙을 두고 addNum을 할 때 왼쪽 오른쪽 순으로 번갈아가며힙에 수를 넣어준다. 이 때, 왼쪽에 있는 최대힙 원소들은 오른쪽에 있는 최소힙에 있는 원소들보다 모두 작거나 같아야 한다. 따라서 addNum을 할 때 최소힙, 최대힙의 가장 위(앞)에 있는 수를 비교해서 최대힙에 있는 수가 최소힙에 있는 수보다 크다면 두 수를 바꿔서 넣.. 2020. 8. 17.
[테트리스] 18. 다음 블럭 정하는 난수 수정 오늘의 이슈. 이제 간단한 건은 없드아. 기존 문제점 중복되는 블럭이 연속으로 많이 나온다. 3개가 연속으로 나온적도 있다. 무작정 랜덤으로 돌리면 안될듯하다. 다른 테트리스에서는 어떻게 하고 있는지 구글링을 해봤다. https://www.quora.com/Do-Tetris-pieces-spawn-randomly 2001년부터 7 System(random bag)이라는 랜덤 블럭 생성 방법을 사용한다는 글을 보았다. 7은 테트리스에서 사용하는 블럭의 수다. https://tetris.fandom.com/wiki/Random_Generator https://simon.lc/the-history-of-tetris-randomizers 좀 더 상세한 정보를 찾아봤다. (새삼느끼는 인터넷의 위대함) 가방에 7개.. 2020. 8. 16.
[Mono][Feign] 404 error custom throw feign에서 404에러 발생 시 에러 핸들링 Mono.fromCallable { feign.get() } .onErrorReturn(FeignException.NotFound::class.java, null) .subscribeOn(Schedulers.elastic()) Feign 에서 404 에러발생시 FeignException.NotFound 에러를 뱉는다. onErrorReturn으로 이를 catch 하여 원하는 응답값을 반환해준다. 2020. 8. 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.

티스토리툴바