본문 바로가기

Medium174

[leetcode][1219] Path with Maximum Gold 문제 : https://leetcode.com/problems/path-with-maximum-gold/ grid 사이즈 조건이 n, m 2019. 10. 14.
[leetcode][1186] Maximum Subarray Sum with One Deletion 문제 : https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ DP로 해결했다. 연속되는 subarray의 최대합을 구하는 문제인데, 최대 하나의 요소를 삭제해도 된다고 한다. 이 말은 즉, 연속합 혹은 한 칸 떨어진 2개의 subarray의 합들 중 최대값을 구하는 문제이다. 2개를 구해야하므로 2차원 배열이 필요하다. dp[0][i] = i번째 요소를 시작기점으로 contiguous max sum. dp[1][i] = i~끝 범위에서 구한 subarray에서 하나의 요소를 삭제했을 때 max sum. 채워야 되는 배열은 위와 같다. // now = arr[i] // 최대값(now, now를 포함하고 (i+1)을 시작점으로 가지는 .. 2019. 10. 5.
[leetcode][1209] Remove All Adjacent Duplicates in String II 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ {문자, 문자가 연속으로 나온 횟수}를 요소로 하는 stack을 하나 만든다. 문자열 s를 앞에서부터 탐색하면서 스택이 비어있거나 스택 top에 있는 요소의 문자가 탐색중인 문자와 같다면 top 요소의 문자가 연속으로 나온 횟수를 +1 해준다. 그리고 만약 스택 top의 연속 횟수가 k와 같다면 stack을 pop 시킨다. 모든 문자열 s를 탐색하면서 stack을 세팅했다면 stack을 pop하면서 정답 문자열 앞에 문자열을 추가하면서 정답을 구할 수 있다. 시간 복잡도는 O(N). (N = |s|) 소스코드 : https://github.com/fpdjsns/A.. 2019. 10. 3.
[leetcode][1190] Reverse Substrings Between Each Pair of Parentheses 문제 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1190.%20Reverse%20Substrings%20Between%20Each%20Pair%20of%20Parentheses.cpp 스택을 사용했다. Example 3: "(ed(et(oc))el)" 을 예로들어보자. 여는 괄호가 시작될때마다 스택을 하나씩 생성해서 이후에 나오는 문자들을 최근 스택에 쌓는다. 스택이 하나도 없는 경우 문자열 순서에 변경이 없을 것이기 때문에 정답 문자열의 뒤에 추가한다. 닫는 괄호가 나오면 최근 스택을 pop하면서 이전 스택에 push한다. 스택을 pop할때 이전 스택이 없는 경우 (스택이 하나인 경우) 정답 문자열에 추가한다. 시간복잡도는 O(|s|^2).. 2019. 10. 1.
[leetcode][1202] Smallest String With Swaps 문제 : https://leetcode.com/problems/smallest-string-with-swaps/ 만약 [(1,3), (1,2)] 라는 pairs 배열이 입력으로 주어진다면 s[1], s[2], s[3] 에 있는 문자들은 direct로는 아니더라도 서로 change 할 수 있다. ex) (2, 3) 을 바꾸려면 (1, 3), (1,2) (1,3)을 바꾸면 (2,3)을 바꾼 결과가 된다. 따라서 Union-Find로 문제를 풀 수 있다. 모든 pairs를 탐색하면서 Union-Find로 한 다리 건너서라도 바꿀 수 있는 인덱스들을 그룹으로 묶는다. 같은 그룹은 속한 그룹의 s 문자열의 최소 인덱스를 가진다. 위 예제에서는 [[0], [1,2,3]] 으로 묶일 것이다. 그룹으로 다 묵었으면 k.. 2019. 9. 23.
[leetcode] 1191. K-Concatenation Maximum Sum 문제 : https://leetcode.com/problems/k-concatenation-maximum-sum/ A : arr 배열 내 앞에서부터 최대부분합 B : arr 배열 내 뒤에서부터 최대부분합 C : arr 배열 내 최대부분합 D : arr 배열 총합 이라고 하자. 정답이 가능한 경우는 위와 같다. 위 그림에서 한 칸이 배열 arr이라고 했을 때 1. B D D D A 2. D D D D D 3. C 4. B A 이 네가지 중 최대 값이 정답이 된다. 시간복잡도는 O(arr.length + k) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1191.%20K-Concatenation%20Maximum%20Sum.cpp 2019. 9. 16.

티스토리툴바