본문 바로가기
반응형

HARD37

[leetcode] 1293. Shortest Path in a Grid with Obstacles Elimination 문제 : https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ m x n 정수 2차원 배열이 주어진다. 각 셸은 0(비어있음) 혹은 1(장애물) 이다. 최대 k개의 장애물을 제거할 수 있다고 할 때, (0, 0) -> (m-1, n-1)로 이동할 수 있는 최소 걸음 수를 구하라. 배열에서 1칸 이동을 1 걸음수로 본다. 상하좌우로 한 칸씩 이동할 수 있다. 불가능한 경우 -1을 반환하라. BFS로 풀었다. 탐색했는지 여부를 저장하기 위해 visits[x][y][k] 배열을 하나 만든다. visits[x][y][k] = 장애물 제거가능 횟수가 k번 남았을 때, grid[x][y]를 탐색한 적이 있는지 여부. BFS.. 2021. 9. 26.
[leetcode] 115. Distinct Subsequences 문제 : https://leetcode.com/problems/distinct-subsequences/ 문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라. 답은 32비트 부호있는 정수임을 보장한다. DP로 풀었다. dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우) dp[i][j] (s[i] 가 t[j]가 아닌 경우) 점화식은 위와 같다. s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로 dp[i-1][j]에 dp[i-1][j-1]을 더해준다. ex) s = "rabbbit", .. 2021. 9. 19.
[leetcode] 446. Arithmetic Slices II - Subsequence 문제 : https://leetcode.com/problems/arithmetic-slices-ii-subsequence/ 정수 배열 nums가 주어지면 모든 arithmetic subsequences 의 수를 구하라. 시퀀스들의 숫자가 3개 이상이고 연속되는 두 요소의 차이가 동일한 경우 arithmetic subsequences라 한다. i:j->(j-i)가 차이이고 i, j를 포함하는 subsequences 수 (i>j) 4:2->1 [4,2] 6:2->1 [6,2] 6:4->2 [6,4,2] [6,4] 8:2->1 [8,2] 8:4->1 [8,4] 8:6->3 [8,6,4,2] [8,6,4] [8,6] 10:2->1 [10,2] 10:4->1 [10,4] 10:6->2 [10,6,2] [10,6].. 2021. 9. 11.
[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.
[leetcode] 587. Erect the Fence 문제 : https://leetcode.com/problems/erect-the-fence/ Erect the Fence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 볼록껍질 (Convex hull) 구하는 문제이다. 볼록껍질..! 5년 전쯤에 한 번 풀어보고 이후로 처음인거 같다. 나무들 중 반드시 정답에 포함될 수 있는 나무는 좌하단(가장 왼쪽에 있는 점들 중 가장 아래) 아니면 우상단(가장 오른쪽에 있는 점들 중 가장 위)에 있는 나무이다. 따라서 이.. 2021. 9. 4.
[leetcode] 76. Minimum Window Substring 문제 : https://leetcode.com/problems/minimum-window-substring/ 길이가 m, n인 문자열 s, t가 입력으로 주어진다. t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구해라. 정답이 없다면 빈 문자열 반환. 투포인터로 풀었다. t문자열의 모든 문자들의 갯수를 저장하는 cnt 배열을 만들어 세팅한다. right 인덱스를 증가시키며 cnt 배열의 등장갯수를 모두 충족시킨다면 해당 right 인덱스를 부분문자열 끝으로 할 때, 해당 부분문자열을 최소 길이로 만들기 위해 left인덱스를 조정한다. left 인덱스는 0부터 증가시키며 현재 탐색중인 문자가 부분문자열에서 제외된다면 cnt 배열의 문자 갯수를 충족시킬 수 없을때까.. 2021. 8. 16.
반응형