본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][1266] Minimum Time Visiting All Points 문제 : https://leetcode.com/problems/minimum-time-visiting-all-points/ 두 점 사이의 거리 = | x점 사이의 거리 | + | y점 사이의 거리 | potints를 앞에서부터 탐색하면서 두 점 사이의 거리들의 합을 구하면 정답이 된다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1266.%20Minimum%20Time%20Visiting%20All%20Points.py 이제부터는 파이썬으로 풀도록 노력해봐야겠다. 2019. 12. 7.
[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][1207] Unique Number of Occurrences 문제 : https://leetcode.com/problems/unique-number-of-occurrences/ set, map을 사용. arr 배열을 탐색하면서 set에 arr[i]들을 저장한다. map은 arr[i]이 나온횟수를 저장하는 cnt, cnt의 value가 나온 횟수를 저장하는 num. 총 2개의 map을 준비한다. 즉, arr = { 1, 2, 2, 1, 1, 3, 2 } 이라면 cnt = { (1, 3), (2, 3), (3, 1) } num = { (1,1), (3, 2) } 이 된다. arr 배열을 탐색하면서 map1, map2개를 세팅한다. 그리고 num[i] = 1 이 되는 모든 i의 개수(uniqueNumCnt)를 구한다. 위 예제에서는 1이 된다. 만약 uniqueNumC.. 2019. 10. 2.
[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.

티스토리툴바