본문 바로가기

알고리즘 문제408

[leetcode] 446. Arithmetic Slices II - Subsequence 문제 : https://leetcode.com/problems/arithmetic-slices-ii-subsequence/ 정수 배열 nums가 주어지면 모든 arithmetic subsequences 의 수를 구하라. 시퀀스들의 숫자가 3개 이상이고 연속되는 두 요소의 차이가 동일한 경우 arithmetic subsequences라 한다. i:j->(j-i)가 차이이고 i, j를 포함하는 subsequences 수 (i>j) 4:2->1 [4,2] 6:2->1 [6,2] 6:4->2 [6,4,2] [6,4] 8:2->1 [8,2] 8:4->1 [8,4] 8:6->3 [8,6,4,2] [8,6,4] [8,6] 10:2->1 [10,2] 10:4->1 [10,4] 10:6->2 [10,6,2] [10,6].. 2021. 9. 11.
[leetcode] 764. Largest Plus Sign 문제 : https://leetcode.com/problems/largest-plus-sign/ 왼쪽 -> 오른쪽. 오른쪽 -> 왼쪽. 위 -> 아래. 아래 -> 위 로 탐색하면서의 subSum을 모든 위치에서 구한다. (x,y)를 + 부호의 가운데 지점이라 할 때, (x,y)를 좌표로한 4가지 subSum들의 최소값이 + 부호의 최대 크기이다. 모든 (x,y)을 + 부호의 가운데라 가정하고 subSum들을 이용하여 + 부호의 크기들을 구했을 때 최대값이 정답이 된다. 시간복잡도는 O(N^2) 공간복잡도는 4가지 subSum들을 구해둬야 하기 때문에 O(4N^2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/764.%2.. 2021. 9. 9.
[LeetCode] 899. Orderly Queue 문제 : https://leetcode.com/problems/orderly-queue/ 문자열 s, 정수 k가 주어진다. 문자열 s의 앞에서부터 k개의 문자들 중 하나를 s문자열의 가장 뒤로 이동시킬 수 있다. 이동횟수와 상관없이 s 문자열의 문자를 이동시켰을 때 얻을 수 있는 문자열들 중 사전순으로 가장 빠른 문자열을 구하라. K가 2이상인 경우, s문자열의 문자들로 만들 수 있는 사전순으로 가장 빠른 문자열이 정답이 될 수 있다. (정렬된 문자열이 정답) 왜냐하면 K가 2이상의 경우 문자들의 개수가 달라지지 않는 한에서 어떤 문자열들도 만들 수 있기 때문이다. 증명해보자. 한 번에 많은 것을 하지 않고 하나의 문자만 올바른 위치로 옮긴다고 생각하면 쉽다. 옮겨야 될 문자를 가장앞에 keep해뒀다가 .. 2021. 9. 5.
[leetcode] 587. Erect the Fence 문제 : https://leetcode.com/problems/erect-the-fence/ Erect the Fence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 볼록껍질 (Convex hull) 구하는 문제이다. 볼록껍질..! 5년 전쯤에 한 번 풀어보고 이후로 처음인거 같다. 나무들 중 반드시 정답에 포함될 수 있는 나무는 좌하단(가장 왼쪽에 있는 점들 중 가장 아래) 아니면 우상단(가장 오른쪽에 있는 점들 중 가장 위)에 있는 나무이다. 따라서 이.. 2021. 9. 4.
[leetcode] 565. Array Nesting 문제 : https://leetcode.com/problems/array-nesting/ 길이가 n인 정수 배열 nums가 주어진다. nums는 [0, n-1] 범위의 겹치지 않는 숫자의 수열이다. s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]] ...} 라 할 때, s[k]의 모든 요소들의 중복이 있지 않아야 한다. 만들 수 있는 s[k]의 최대 길이를 구하라. nums 배열은 유니크한 숫자들로 이루어져있기 때문에 s[k]배열은 사이클이 만들어진다. 예를 들어, nums = {1, 2, 0, 3} 이라면 s[k]가 될 수 있는 배열들은 {1,2,0}, {3}이고 이들은 각각 사이클이 만들어진다. 즉 사이클이 만들어지는 s 배열을 만드는데 이 배열들 중 최장 .. 2021. 9. 3.
[leetcode] 76. Minimum Window Substring 문제 : https://leetcode.com/problems/minimum-window-substring/ 길이가 m, n인 문자열 s, t가 입력으로 주어진다. t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구해라. 정답이 없다면 빈 문자열 반환. 투포인터로 풀었다. t문자열의 모든 문자들의 갯수를 저장하는 cnt 배열을 만들어 세팅한다. right 인덱스를 증가시키며 cnt 배열의 등장갯수를 모두 충족시킨다면 해당 right 인덱스를 부분문자열 끝으로 할 때, 해당 부분문자열을 최소 길이로 만들기 위해 left인덱스를 조정한다. left 인덱스는 0부터 증가시키며 현재 탐색중인 문자가 부분문자열에서 제외된다면 cnt 배열의 문자 갯수를 충족시킬 수 없을때까.. 2021. 8. 16.

티스토리툴바