본문 바로가기

알고리즘 문제/Leetcode283

[leetcode] 1328. Break a Palindrome 문제 : https://leetcode.com/problems/break-a-palindrome/ 소문자 영어로 이루어진 펠린드롬 문자열이 주어지면 한 문자만 다른 소문자 알파벳으로 변경하여 펠린드롬이 아닌 문자열로 만들고자 한다. 이 때, 사전순으로 가장 작은 문자열을 구하라. 만일 조건을 만족하는 변경 가능한 문자열이 없는 경우 빈 문자열을 반환하라. 펠린드롬이므로 1/2 개만 탐색해도 된다. (앞뒤 문자가 같으므로) 문자열이 홀수인 경우 가운데 문자는 펠린드롬 여부와 관계가 없으므로 변경하는 문자에서 제외시켜야 한다. -> 문자열 길이가 1인 경우 빈문자열을 반환한다. (어떤 문자를 바꿔도 펠린드롬이 되므로) 앞에서 1/2개의 문자들 중 ‘a’가 아닌 문자가 있으면 이를 ‘a’로 바꾼다. (앞에 문.. 2021. 9. 25.
[leetcode] 1137. N-th Tribonacci Number 문제 : https://leetcode.com/problems/n-th-tribonacci-number/ T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3) n이 주어질 때, T(n) 값을 구해라. n크기의 배열을 만들어서 문제에서 주어진 점화식으로 구할 수 있다. 이 경우, 시간/공간 복잡도는 모두 O(n)이 된다. 점화식을 보면 결국 필요한 값들은 최신 값 3개 이므로 크기가 3인 배열(let, arr)을 만들고 arr[n%3] = arr[0] + arr[1] + arr[2] 위 식으로 arr을 채워나간 뒤 n번째까지 모두 채우면 arr[n%3] 가 정답이 된다. 이 경우 시간복잡도는 동일하게 O(n)이지만 공간복잡도는 O(1)이 된다. 소스.. 2021. 9. 25.
[leetcode] 115. Distinct Subsequences 문제 : https://leetcode.com/problems/distinct-subsequences/ 문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라. 답은 32비트 부호있는 정수임을 보장한다. DP로 풀었다. dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우) dp[i][j] (s[i] 가 t[j]가 아닌 경우) 점화식은 위와 같다. s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로 dp[i-1][j]에 dp[i-1][j-1]을 더해준다. ex) s = "rabbbit", .. 2021. 9. 19.
[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.

티스토리툴바