본문 바로가기

알고리즘 문제/Leetcode283

[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.
[leetcode] 1632. Rank Transform of a Matrix 문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/ m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라. 순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다. 1. p q : rank(p) > rank(q) 랭크는 가능한한 작게 매겨져야 한다. 예시 4를 보자. 7 3 6 1 4 5 9 8 2 만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다. 요소 값을 기준으로 오름차순 정렬한다. 요소값(x, y) 1 (1,0) -> 2.. 2021. 8. 12.
[leetcode] 415. Add Strings 문제 : https://leetcode.com/problems/add-strings/ 가산기 구현 문제. 학창시절에 배운적이 있는데 그때의 기억을 되살려서.. carry 변수를 하나 둔다. 올림되는 수가 있다면 1, 아니면 0일 것이다. 입력 문자열 num1, num2의 인덱스 변수를 ind1, ind2로 두고 해당 변수들은 입력문자열의 가장 뒤의 인덱스를 초기화 값으로 가진다. 덧셈뺄셈을 할 때, 같은 자리수에 있는 수들을 더해야 하기 때문이다. num1[ind1], num2[ind2]를 각각 변수 a, b라 하자. 만일 ind1, ind2가 문자열 num1, num2의 인덱스 범위를 넘어선다면(0 미만) 0으로 본다. 탐색 후 ind1, ind2를 1씩 감소시킨다. a + b + carry 를 나누기.. 2021. 8. 11.
[leetcode] 132. Palindrome Partitioning II 문제 : https://leetcode.com/problems/palindrome-partitioning-ii/ 문자열 s가 주어지면 s를 잘라 부분문자열들을 만들었을 때 모든 부분문자열들이 펠린드롬이 되는 최소 절단횟수를 구하여라. 먼저 DP로 2차원 배열을 만들어 펠린드롬[i][e] = 문자열[i,e]가 펠린드롬인지를 구한다. 펠린드롬[i][j] = 펠린드롬[i+1][j-1] (s[i] == s[j]) = false (s[i] != s[j]) 문자열[i~j]은 문자열의 첫문자와 끝 문자가 다르면 false, 첫문자와 끝문자가 같다면 문자열[i+1, e-1]이 펠린드롬인 경우는 펠린드롬, 아니면 펠린드롬이 아니다. 위 점화식으로 펠린드롬 여부를 구하면 이번엔 1차원 배열을 만든다. dp[i] = s[0.. 2021. 8. 7.

티스토리툴바