본문 바로가기

HARD56

[leetcode] 1463. Cherry Pickup II 문제 : https://leetcode.com/problems/cherry-pickup-ii/ rows x cols 체리 필드(grid)가 주어지고 각 요소값은 체리 수를 의미한다. 로봇1은 왼쪽 상단 (0,0)에서 출발하고 로봇2는 오른쪽 상단 (0, cols-1)에서 출발한다. 셀 (i,j)에서 로봇은 (i+1, j-1), (i+1, j), (i+1, j+1) 3가지 중에 한 곳으로 이동할 수 있다. 두 로봇이 동일한 셀에 있을 때 한 로봇만 체리를 가져갈 수 있다. 로봇들이 이동할 때, 수집할 수 있는 체리의 최대 수를 구해라. DP로 풀 수 있다. dp[row][col1][col2] = 로봇1은 (row, col1), 로봇2는 (row, col1)에 있을 때 수집가능한 체리수의 최대값. dp[ro.. 2022. 1. 11.
[Leetcode] 902. Numbers At Most N Given Digit Set 문제 : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/ 내림차순으로 정렬된 숫자 배열 digits와 정수 n이 주어진다. digits 배열의 숫자는 원하는 만큼 재사용 가능하다. digits 수들을 이용하여 숫자를 만들 때, 정수 n보다 작거나 같은 정수들의 갯수를 구하라. 예시를 직접 풀면서 알아보자. digits = ["1", "3", "5"], n = "355" 입력 값이 위와 같을 때, 일의 자리(x), 십의 자리(xx) 수들은 모두 정답에 포함된다. 따라서 이들 개수는 정답에 미리 더해둔다. x 에 digits 들 중 어느 숫자가 와도 상관없으므로 조합을 생각하면 각 자리에 3개의 수가 올 수 있으므로 일의 자리의 경우의 수는.. 2021. 12. 19.
[Leetcode] 1032. Stream of Characters 문제 : https://leetcode.com/problems/stream-of-characters/ 문자열 리스트 words가 입력으로 주어지고 추가될 알파벳 소문자가 한 글자씩 입력으로 들어온다. 추가될 알파벳들은 초기 빈문자열에서 뒤에 하나씩 추가된다. 알파벳이 하나씩 추가되어 만들어진 문자열의 접미사가 words 배열에 존재하는지 판단해라. 트라이(Trie)를 만들어야 한다. words 문자열들을 뒤에서 부터 탐색하면서 트라이를 만들어간다. 예를 들어, words = ["abc", "bc", "dc"] 인 경우 [그림 1]과 같은 트라이가 만들어진다. 1번 노드가 트라이의 헤드 노드이며 빨간색 체크한 부분이 문자열의 끝을 의미한다. 알파벳들을 하나씩 받으며 만들어진 문자열을 마찬가지로 뒤에서부터 .. 2021. 12. 4.
[Leetcode] 1526. Minimum Number of Increments on Subarrays to Form a Target Array 문제 : https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/ 양의 정수 배열 target과 동일한 크기의 초기값이 모두 0인 initial 배열이 있다. 한 번의 연산에서 initial 배열의 하위배열의 요소값들을 1씩 증가시킬 때, initial 배열에서 target 배열로 만들 수 있는 최소 연산 횟수를 구하라. 결국은 어느 부분을 하위 배열로 묶을 것인지를 찾는게 중요하다. target 배열을 앞에서부터 탐색하면서 이전 값 보다 탐색 중인 값이 더 큰 경우 이전 값과의 차이(하위 배열을 제외하고 추가로 증가되어야 하는 수)를 정답에 더해준다. 탐색하는 값이 이전 값보다 같거나 작다.. 2021. 11. 30.
[Leetcode] 952. Largest Component Size by Common Factor 문제 : https://leetcode.com/problems/largest-component-size-by-common-factor/ 고유한 양의 정수 배열 nums가 주어진다. nums[i], nums[j] (i != j)는 1보다 큰 공약수를 공유할 때서로의 노드는 연결되어있다. 그래프에서 가장 큰 연결 컴포넌트의 크기를 구하라. 동일한 약수를 가지는 노드를 연결해야 한다. -> Union-Find 를 사용하자. nums 배열 중 가장 큰 정수를 구한 뒤 그 크기만큼의 부모 배열을 만든다. nums 배열을 차례대로 탐색(let, num)하면서 1보다 큰 약수를 구해야하므로 2부터 탐색중인 정수의 루트까지(let, i) 2중 for 문으로 탐색한다. 만일 num이 i로 나누어떨어진다면 i와 num/i.. 2021. 11. 23.
[Leetcode] 668. Kth Smallest Number in Multiplication Table 문제 : https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ m x n 크기의 2차원 배열(1-indexed)이 있다. 배열 값은 각 요소들의 행, 열 인덱스의 곱이다. m, n, k가 주어졌을 때, m x n 2차원 배열에서 k 번째로 작은 요소 값을 구해라. k 번째로 작은 요소 값은 완탐을 하지 않는 이상 구하기 어렵기 때문에, 정수 x 보다 작은 요소 값들이 몇 개인지 구해보자. m = 3, n = 3, k = 4을 예로 들어보자. 1 2 3 2 4 6 3 6 9 1 2 2 3 3 4 6 6 9 구하고자 하는 문제를 좀 더 분해해서 각 행에서 정수 x 보다 작은 요소 값들이 몇 개(let, cnt)인지를 먼저 구해보.. 2021. 11. 16.

티스토리툴바