알고리즘 문제/Leetcode283 [Leetcode][665] Non-decreasing Array 문제 : leetcode.com/problems/non-decreasing-array/ 정수형 배열이 주어질 때 최대 한 개의 요소를 수정하여 감소하지 않는 배열을 만들 수 있는지를 구하라. 만들고자 하는 배열은 증가하는 배열이 아닌, 감소하지 않는 배열이므로 증가하는 수를 찾아 바로 앞이나 뒤에 있는 요소와 같은 수로 변경시킨다. (기본 아이디어) 앞에서부터 배열을 탐색하면서 탐색 중인 인덱스가 i일 때, nums[i] > nums[i+1] (감소하는 구간)인 경우 i를 변수를 만들어 저장해둔다. (let, ind). 만일 ind 변수가 2번 이상 세팅되려고 할 땐 두 개의 요소를 수정해야 하므로 감소하지 않는 배열을 만들 수 없다. 모든 배열을 탐색했을 때, ind 변수가 세팅된적이 없거나 (모든 요.. 2021. 5. 8. [Leetcode][970] Powerful Integers 문제 : https://leetcode.com/problems/powerful-integers/ 1이상의 양수인 x, y, 0이상의 bound가 입력으로 주어진다. i, j 가 0이상의 양수라 할때, x^i + y^i 2021. 5. 1. [Leetcode][696] Count Binary Substrings 문제 : https://leetcode.com/problems/count-binary-substrings/ 0과 1로 이루어진 문자열에서 연속적으로 같은 숫자의 문자가 나오는 부분문자열들의 수를 구하라. 부분문자열 예 : 0011, 01, 10 / 안되는 예 : 1010 (같은 숫자가 연속적이지 않음). 11100 (숫자들의 등장횟수가 다름) 동일한 부분 문자열이라도 여러번 발생하면 발생한 횟수만큼 정답에 더해준다. 문자열을 탐색하면서 연속적으로 나오는 0과 1의 수를 센다. 예를 들어, "00110011"이라면 인덱스 / 숫자 0 1 0 (0) 1 0 1 (0) 2 0 2 (1) 2 1 3 (1) 2 2 4 (0) 1 2 5 (0) 2 2 6 (1) 2 1 7 (1) 2 2 위와 같이 채워진다. 인덱스.. 2021. 4. 24. [Leetcode][1074] Number of Submatrices That Sum to Target 문제 : leetcode.com/problems/number-of-submatrices-that-sum-to-target/ 2차원 배열 matrix와 target 정수가 주어진다. matrix[x][y] (x1 2021. 4. 18. [Leetcode][86] Partition List 문제 : https://leetcode.com/problems/partition-list/ 리스트노드의 head와 정수 x가 주어질 때, x보다 작은 val를 가진 노드들(let, left)은 왼쪽, x와 같거나 큰 val를 가진 노드들(let, right)은 오른쪽으로 정렬된 리스트노드의 헤드를 구하라. 이 때, left, right 그룹 내에서의 노드들은 기존 정렬 순서가 유지되어야 한다. x보다 작은 val 를 가진 노드들을 저장하는 리스트 노드(left)와 x와 같거나 큰 val를 가진 노드들을 저장하는 리스트 노드(right)를 분리시킨다. 만일 left 리스트 노드가 비어있다면 right 리스트 노드의 헤드를 반환한다. left 리스트노드가 비어있지 않다면 left 리스트노드의 마지막 노드의 .. 2021. 4. 14. [Leetcode][17] Letter Combinations of a Phone Number 문제 : leetcode.com/problems/letter-combinations-of-a-phone-number/ 전화 버튼과 동일한 숫자와 문자의 매핑이 있다. 2~9까지의 숫자로 이루어진 문자열이 주어지면 가능한 모든 문자 조합을 반환해라. 하나의 숫자에 복수개의 문자가 매핑되므로 dict[숫자] = 문자의 배열 을 먼저 구해준다. 가능한 문자 조합들은 백트래킹을 이용하여 구한다. 예시로 주어진 23이면 1. 빈 문자열부터 시작해서 2에 해당하는 문자들 중 하나를 넣고("a") 다음 숫자를 판단한다. 2. "a" 이후 3에 해당하는 문자들 중 하나를 세팅한다. "ad". 모든 digits들의 숫자를 판단했으므로 "ad"를 정답에 추가한다. 3. 가장 마지막 문자를 제거한 후('d'가 제거되어 "a.. 2021. 4. 10. 이전 1 ··· 20 21 22 23 24 25 26 ··· 48 다음
