알고리즘 문제408 [Leetcode] 936. Stamping The Sequence 문제 : https://leetcode.com/problems/stamping-the-sequence/ 이전에 찍힌 스탬프는 덮히고 가장 마지막에 찍히는 스탬프가 최종 글자가 된다. 따라서 뒤에 찍힐수록 중요하게 봐야하는 값이 되므로 스탬프가 찍히는 역순으로 생각한다. 예를 들어 stamp="abc", target="ababc"라면 2번째 자리에 "abxxx" 로 x자리가 스탬프가 찍히고 스탬프가 찍힌 x 자리는 어느 문자가 오든 관계없는 자리가 된다. 따라서 0번째에 스탬프를 찍는다. 그럼 [2, 0]으로 도장이 찍히는데 역순으로 생각한 것이기 땜문에 [0, 2]가 정답이 된다. [0, 2] 로 도장을 찍은 경우 _ _ _ _ _ -> a b c _ _ -> a b a b c 가 된다. 따라서 targ.. 2022. 8. 21. [Leetcode] 792. Number of Matching Subsequences 문제 : https://leetcode.com/problems/number-of-matching-subsequences/ 문자열 s를 탐색하면서 특정 문자들의 인덱스들을 오름차순 배열에 저장해둔다. (charIndexes = 2차원 배열, charIndexes['a'] = 'a' 문자들의 등장인덱스 리스트) ex) s="abacb" => charIndexes['a'] = [0, 2], charIndexes['b'] = [1, 4], charIndexes['c']=[3] words 배열의 단어들의 문자를 앞에서부터 탐색하면서 탐색중인 문자가 문자열 s의 subsequences인지 확인해보자. words를 앞에서부터 탐색하면서 최근에 탐색한 s 인덱스를 index 배열에 저장해둔다. words[i] = c .. 2022. 7. 20. [Leetcode] 629. K Inverse Pairs Array 문제 : https://leetcode.com/problems/k-inverse-pairs-array/ inverse pairs : 0 nums[j] 조건을 만족하는 [i, j]. DP[n][k] = n 크기의 nums 배열이 있을 때 k 개의 inverse pairs 를 가지는 경우의 수. n-1 크기의 nums에서 어떻게 n 크기의 nums를 만들 수 있는지 먼저 살펴보자. [그림 1] 에서 n=4, k=1인 경우는 왼쪽 아래와 같이 총 3가지 방법이 있다. 3가지 리스트들에서 4인 원소들을 제거하면 오른쪽과 같은 리스트들이 나온다. 여기에서 추론 가능한건 n-1 크기의 배열에서 추가되는 4의 위치에 따라 k(inverse pairs)의 크기가 달라진다는 것이다. 예를 들어보자. [그림 2] 에서 [.. 2022. 7. 17. [Leetcode] 1647. Minimum Deletions to Make Character Frequencies Unique 문제 : https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/ 문자열 s는 동일한 빈도를 가진 두 개의 다른 문자가 없으면 good이라 한다. 문자열 s 가 주어지면 s를 good 이라고 불리기 위해 삭제해야 하는 최소 문자 수를 구해라. 문자들의 빈도를 구한 뒤 배열에 저장해서 내림차순 정렬한다. "aaaabccccd" -> [4, 4, 1, 1] 배열을 탐색하면서 가능한 최대 빈도수를 구한 뒤 이와 비교하여 삭제해야 하는 문자 수를 구한다. 초기 최대 빈도 수는 배열의 첫번째 원소와 같다. 가능 최대 빈도수는 파란색의 경우 "가능 최대 빈도 수 - 1"로 갱신된다. 빨간 색의 경우 "탐색 중인 빈도 수.. 2022. 6. 28. [Leetcode] 1423. Maximum Points You Can Obtain from Cards 문제 : https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/ 여러 장의 카드가 한 줄로 배열되어 있다. 각 카드에는 연관된 점수가 있다. 이 배열을 cardPoints라 한다. 한 단계에서 배열의 가장자리, 최좌측, 최우측 중 한 곳에서 한 장의 카드를 가져올 수 있다. 총 k번의 단계를 거쳐, 총 k개의 카드를 가져와야 한다고 할 때 얻을 수 있는 최대 점수를 구해라. 오른쪽으로 부터 k개의 합을 구해둔뒤, 왼쪽부터 선택하는 카드 수를 0부터 k개까지 탐색하면서 나올 수 있는 점수들의 합을 구한 뒤 이들 중 최대값이 정답이 된다. 예시 cardPoints = [4, 3, 1, 9, 1], k = 3. 그림 보면 이해하실거라 생.. 2022. 6. 26. [Leetcode] 630. Course Schedule III 문제 : https://leetcode.com/problems/course-schedule-iii/ 소요기간(연속), 완료되어야 하는 기간을 가진 course들의 배열 courses이 입력으로 주어진다. 1일차부터 시작하고 2개의 코스를 한 번에 들을 수는 없다. 수강할 수 있는 최대 코스 수를 구하라. courses 배열을 완료되어야 하는 기간의 오름차순으로 정렬한다. 우선순위큐를 만든다. 이 큐에는 현재까지 수강가능한 최대 코스 수를 가지는 코스들의 수강기간(duration)로 이루어져 있다. (왜 duration을 넣는지는 뒤에서 설명할 예정(1)) 큐에 있는 코스들을 모두 수강했을 때 쇼요기간을 day 변수에 저장해둔다. 정렬된 courses 배열을 앞에서부터 탐색하면서 큐에 넣을 수 있는지 판단.. 2022. 6. 24. 이전 1 2 3 4 5 6 7 ··· 68 다음
