알고리즘 문제408 [Leetcode] 410. Split Array Largest Sum 문제 : https://leetcode.com/problems/split-array-largest-sum/ 음이 아닌 정수로 이루어진 nums 배열과 양수 m 이 주어졌을 때, nums 배열을 비어있지 않은 m개의 연속 하위 배열로 분할 할 수 있다. 분할한 m개의 부분배열 중 가장 큰 합을 최소화 했을 때, 부분배열 합의 최대값을 구해라. 이진탐색으로 풀었다. 부분배열 중 가장 큰 합(set, answer)을 이진탐색을 통해서 구하는 방법으로 해보자. answer가 될 수 있는 값은 제한사항을 보면 nums[i]의 최소값이 0이므로 0에서 nums배열의 합까지 가능하다. 따라서, left = 0, right = sum of nums. 로 한 후 이진탐색을 돌린다. 이진탐색은 medium = (left .. 2022. 3. 31. [Leetcode] 74. Search a 2D Matrix 문제 : https://leetcode.com/problems/search-a-2d-matrix/ m x n 정수형 배열 matrix 가 있을 때, 아래 2가지 조건을 만족한다. - 정수는 각 행에서 왼쪽에서 오른쪽으로 오름차순 정렬되어 있다. - 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 크다. target 값이 주어질 때, matrix에서 target이 존재하는지 구해라. matrix 의 최상당 최우측에 있는 요소부터 탐색해나간다. 탐색중인 인덱스를 row, col 이라 하자. 만약 matrix[row][col]이 target과 같다면 target이 존재한다는 뜻이므로 true를 반환한다. 만약 matrix[row][col]이 target보다 크다면 col을 1 감소시킨다. 만약 matrix.. 2022. 3. 31. [Leetcode] 1663. Smallest String With A Given Numeric Value 문제 : https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/ 먼저 n 개의 a로 문자열을 만든 다음 가장 뒤에서부터 남은 k 만큼 문자열의 뒤에서부터 더한다. 예를 들어, n=3, k=27인 경우, "aaa"를 만든다. 남은 k는 24이다. 이를 뒤에서부터 더해나가면 "aay"가 된다. n=5, k=73인 경우, "aaaaa", k = 68으로 초기값을 세팅한다. 가장 뒤에 있는 문자에 25를 더해 "aaaaz", k=43. "aaazz", k=18 "aaszz", k=0. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1.. 2022. 3. 22. [Leetcode] 763. Partition Labels 문제 : https://leetcode.com/problems/partition-labels/ 배열(arr)을 하나 만들어서 문자열 S에서 알파벳이 나오는 시작인덱스와 끝인덱스를 저장한다. S문자열을 탐색하면서 배열을 다 채운뒤 오름차순 정렬한다. 정렬한 배열을 앞에서부터 탐색하면서 나눌수 있는 부분문자열의 마지막 인덱스(last)를 구한다. 1. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 작다면 이 알파벳도 부분문자열에 속해야 한다. 알파벳의 종료 인덱스가 last보다 크다면 갱신한다. ex) aabbab -> last는 b 인덱스로 갱신 2. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 크다면 이 알파벳은 별도의 부분문자열로 나뉠 수 있다. 이때까지 구한 부분문자열의 길이를 정답에.. 2022. 3. 21. [Leetcode] 316. Remove Duplicate Letters 문제 : https://leetcode.com/problems/remove-duplicate-letters/ 문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복되는 문자를 제거하라. 가능한 결과 문자열들 중 사전순으로 가장 작은 문자열을 구하라. 사전순으로 가장 작은 문자열을 구해야 하므로 앞에 있을수록 작은 문자열이 앞에 가야한다. 즉, 현재 만든 문자열에서 탐색 중인 문자를 추가하고자 할 때 정답 문자열에 있는 문자보다 탐색 중인 문자가 작다면 정답에 추가해주어야 한다. 이를 판단하기 위해 스택을 추가한다. 문자열 s를 앞에서부터 탐색하면서 스택에 정답 문자열을 만들 수 있는 문자들을 넣는다. 사전순으로 앞에 있는 문자열을 만들기 위해서는 앞으로 추가될 문자가 현재 정답문자열에 있는 문자보다 .. 2022. 3. 18. [LeetCode] 856. Score of Parentheses 문제 : https://leetcode.com/problems/score-of-parentheses/ 문자열 S를 앞에서부터 탐색한다. 스택을 사용하는데 여기에는 닫는 괄호가 나와서 유효한 값이 생기면 계산된 양수가 아직 닫는 괄호랑 짝지어지지 않은 여는 괄호는 0을 저장한다. 탐색 중 여는 괄호가 나오면 스택에 0을 push 한다. 닫는 괄호가 나오면 스택에 있는 수를 탐색하여 해당 닫는 괄호와 짝이 되는 여는 괄호 사이에 있는 괄호들의 두 번째 조건 AB = A + B 를 계산한다. ex) (()()) -> 진한 괄호들의 연산 1 + 1 계산 짝이 되는 여는 괄호는 스택에 존재하는 0 중 가장 위에 있는 값이다. 따라서 스택의 top이 0이 나오기 전까지 pop 되어 나오는 숫자들을 모두 더한다. 모.. 2022. 3. 17. 이전 1 ··· 4 5 6 7 8 9 10 ··· 68 다음
