본문 바로가기

leetcode17

leetcode 778 - Swim in Rising Water https://leetcode.com/problems/swim-in-rising-water/ 풀이 BFS로 현재 상태에서 갈 수 있는 다음 상태를 찾는다. 대신 최단 거리를 찾아야 하므로 현재 상태를 고를 때 모든 상태 중에 가장 좋은 상태를 뽑아야 한다. 가장 좋은 상태는 문제 정의 그대로 최소 시간이다. 이렇게 필요한 { 시간, x좌표, y좌표 } 세 가지를 가지는 set 자료구조를 사용해서 다익스트라를 사용해서 목적지까지의 최소 시간을 구할 수 있다. 모든 위치에 $n^2$에 대해서 set에 insert / erase가 필요하기 때문에 시간 복잡도는 $O(n^2 log n^2)$이다. 코드 class Solution { public: vector dir = {{0,1}, {0,-1}, {1,0}, .. 2020. 10. 7.
leetcode 410 - Split Array Largest Sum https://leetcode.com/problems/split-array-largest-sum/ 풀이 입력된 리스트를 m개로 나눴을 때 sum이 가장 큰 subarray 최소화하는 문제를 한 번에 풀기는 쉽지 않다. 하지만 subarray의 sum이 k가 넘지 않도록 m개로 나눌 수 있냐는 문제는 쉽게 풀 수 있다. sum이 k가 넘지 않는 선까지 최대한 그리디 하게 묶어보면 된다. 그러면 문제를 바꿔서 모든 k에 대해 m개로 나눌 수 있는지 확인하는 방법에서 되는데, 여기서 한단계 더 나아가 파라메트릭 서치를 이용할 수 있다. 정답이 k라고 했을 때 k이하의 수에 대해서는 m개로 나눌 수 있고, k보다 큰 수에 대해서는 나눌 수 없는 특성이 있기 때문이다. 이 k를 이분 검색으로 답을 좁혀가면 된다... 2020. 10. 6.
leetcode 787 - Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops/ 풀이 최대 k번 경유할 수 있기 때문에 아래와 같이 테이블을 정의한다. d[i][j] = 최대 i번 경유해서 j까지 왔을 때 최단 거리 정의한 대로 d[i][j]를 채우기 위해 점화식을 세워보면 j로 갈 수 있는 모든 k에 대해서 아래와 같은 식이 된다. d[i][j] = min(d[i-1][k] + distance(k, j)) 물론 최대 i번 경유라고 정의했기 때문에 처음에 d[i][j] = d[i-1][j]로 초기화를 해두어야 한다. 식을 보면 i번 경유할때 참조하는 데이터는 i-1번 경유한 경우밖에 없다. 따라서 d 배열을 2차원 테이블로 만들 필요 없이 1차원 테이블 2개로 재활용하면서.. 2020. 10. 6.
leetcode 932 - Beautiful Array https://leetcode.com/problems/beautiful-array/ 풀이 $i < k < j$ 일 때 $2\cdot A[k] = A[i] + A[j]$ 를 만족하는 i, k, j가 없는 배열을 구해야 한다. 길이 n짜리 배열 [1, 2, 3, ..., n]이 있을 때 이 조건을 만족하는 배열을 찾기 위해 문제를 나눌 수 있다. [1, 3, 5, ..., (n+1)/2] 배열과 [2, 4, 6, ..., n/2]로 문제를 나눈 다음에 각 배열의 beautiful array를 구했다고 생각해보자. 각 배열 안에서는 정의 그대로 위 조건에 해당하는 i, k, j가 없다. 이때 두 배열을 concat 한 배열에도 그런 i, k, j는 없음이 보장된다. 앞 배열에 i, 뒷 배열에 j가 있을 때 A.. 2020. 10. 6.
leetcode 239 - Sliding Window Maximum https://leetcode.com/problems/sliding-window-maximum/ 풀이 $O(n log k)$ 처음 k구간을 담은 set을 만들어 놓고(중복이 가능하므로 multiset), 이후 한 칸씩 옮길 때마다 다음 값을 insert / 빠지는 값을 erase 했다. 주의할 점은 multiset에서 erase 할 때 value를 넘기면 value 값을 가지는 모든 원소를 삭제하기 때문에 iterator를 넘겨야 한다. https://www.cplusplus.com/reference/set/multiset/erase iterator는 지우려고 하는 value값들 중 아무 값이나 상관없기 때문에 lower_bound로 찾아서 지웠다. 입력으로 들어오는 nums 배열을 순회하면서 모든 원소.. 2020. 10. 6.

티스토리툴바