분류 전체보기657 [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. 코로나 5일차 일지 8/15 월요일 저녁 기침이 나기 시작하고 밤이 되니 감기 몸살이 온 것 마냥 오한이 들었다. 타이레놀을 하나 먹고 10시였지만 이불을 꼭 덮고 잠을 청했다. 8/16 화요일 일어나자마자 이건 코로나다. 라는 생각이 들었다. 체온계로 체온을 재보니 36.4도로 지극히 정상이 나왔다. 하지만 몸살 기운이 있었고 기침이 났기 때문에 일단 회사에 휴가를 내고 조금 더 잤다. 자고 일어나면 좀 괜찮을까 싶었지만 몸상태는 그대로였기에 약국에 가서 타이레놀, 종합감기약, 자가키트를 사서 돌아왔다. 자가키트를 해보니 결과는 양성이었다. 점심시간이 끼어있어 일단 회사메신저로만 상황을 알리고 죽을 시켜 먹었다. 체온을 다시 재보니 38.2도가 나왔다. 자가키트만으로는 코로나에 걸렸다는 증명이 되지 않는다길래 병원을 갈 .. 2022. 8. 19. [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. 이전 1 2 3 4 5 6 7 8 ··· 110 다음
