Medium174 [Leetcode] 2439. Minimize Maximum of Array 문제 : https://leetcode.com/problems/minimize-maximum-of-array/description/ 0부터 인덱싱된 n개의 음이 아닌 정수로 구성된 nums 배열이 제공됩니다. 한 번의 작업에서는 다음을 수행해야 합니다. 1. 1 0 입니다. 2. nums[i]를 1 감소시킵니다. 3. nums[i-1]를 1 증가시킵니다. 작업 수행 후 nums의 최대 정수 값 중 가능한 최소 값을 반환합니다. nums의 최대 정수 값 중 가능한 최소 값을 구하려면 모든 요소들을 평균 값으로 만들면 됩니다. 문제 2, 3번을 통해 알 수 있는 점은 뒤에 있는 nums 요소의 수는 앞으로 이동 가능할 수 있다. 입니다. ex) [1, 2, 3, 4] -> [3, 2, 3, 2] (4의 2를.. 2023. 4. 5. [Leetcode] 2405. Optimal Partition of String 문제 : https://leetcode.com/problems/optimal-partition-of-string/description/ 문자열 s가 주어졌을 때, 각 부분 문자열에 중복되는 문자가 없도록 하나 이상의 부분 문자열로 분할합니다. 즉, 각 문자는 분할된 부분 문자열 안에 최대 하나만 속해야 합니다. 각 분할에서 최소한의 부분 문자열 수를 반환합니다. 그리디로 풀 수 있습니다. 알파벳이 부분 문자열 안에서 등장했는지를 저장하는 배열을 하나 만듭니다. 문자열을 앞에서부터 탐색하면서 해당 배열을 갱신해나갑니다. 만약 탐색중인 문자가 이미 등장했다면 배열을 다시 false로 초기화 시키고 부분 문자열 수를 하나 증가시킵니다. 모든 문자열을 탐색했을 때 부분 문자열 수가 정답이 됩니다. 시간복잡도는 .. 2023. 4. 4. [Leetcode] 623. Add One Row to Tree 문제 : https://leetcode.com/problems/add-one-row-to-tree/ 루트부터 자식으로 탐색해가면서 현재 depth가 새로운 노드가 추가되어야 하는 위치의 부모 노드라면 (1) (depth-1 이라면) 새로운 노드를 만들고 왼쪽 자식 노드에 들어갈 새로운 노드의 왼쪽 자식엔 원래의 왼쪽 자식 노드를 연결(2)한다. 오른쪽 자식 노드에 들어갈 새 노드의 오른쪽 자식엔 원래 오른쪽 자식 노드를 연결(3)한다. 새로 만든 노드들을 탐색 중인 노드의 자식 노드들로 연결(4)한다. 시간 복잡도는 O(N). N = 노트 수 소스코드 https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/623.%20Add%20One%20Ro.. 2022. 10. 5. [Leetcode] 838. Push Dominoes 문제 : https://leetcode.com/problems/push-dominoes/description/ 배열을 하나 만들어서 문자열 길이만큼 0을 채운다. 이 배열에 L이라면 음수를, R이라면 양수를 채울 것이다. '.' 인 경우는 0. 'L', 'R'을 만나서 배열을 갱신할 때 시작점과 얼마나(인덱스) 떨어져 있는지 저장한다. 문자가 'L'이라면 왼쪽으로 가면서 -1, -2, -3 … 이런식으로 다음 문자를 만날 때까지 채워준다. 'R'이라면 오른쪽으로 가면서 1, 2, 3 … 을 다음 문자를 만날 때까지 채워준다. 문자가 있는 부분은 양수나 음수로 적절히 채운다. 나는 L은 '-1', R은 '1'을 채워줬다. 주의할 점이 2가지 있다. 1. "R . . . L" 이 경우 정답은 "R R . L.. 2022. 9. 28. [Leetcode] 1680. Concatenation of Consecutive Binary Numbers 문제 : https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/ 숫자 n의 2진법 자리 수는 log2(n) + 1이다. 1부터 n까지 탐색하면서 이때까지의 합계를 sum이라 하자. 예를 들어, 숫자 5의 숫자 sum의 이진법 뒤에 추가한다고 하면 숫자 5의 이진법은 101. 자리수는 3이다. 따라서 sum을 앞으로 세 칸 움직이고 ( 2022. 9. 24. [Leetcode] 1996. The Number of Weak Characters in the Game 문제 : https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/ 정렬 후, 그리디로 풀었다. 앞에서부터 탐색하면서 탐색중인 요소가 정답이 될 수 있는지 판단해야 한다. 공격, 방어 둘 다가 작아야 하므로. 먼저 공격을 내림차순으로 정렬한다. 공격은 내림차순 정렬했기 때문에 이때동안 탐색했던 모든 요소들의 공격은 현재 탐색하는 요소의 공격보다 크거나 같다(1). 따라서, 현재 탐색중인 방어보다 큰 값이 이때까지 탐색했던 방어들 값 중 있는지만 판단하면 된다. 큰 값을 구해야 하므로 탐색 중에 방어 값들 중 최대 값을 변수(maxDepen)에 저장해두고 이를 비교하면 O(1)만에 비교가능하다. 문제에서 공격, 방어를 비교할 때 str.. 2022. 9. 9. 이전 1 2 3 4 5 ··· 29 다음
