Medium174 [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] 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] 968. Binary Tree Cameras 문제 : https://leetcode.com/problems/binary-tree-cameras/ 이진트리의 루트 노드가 주어진다. 노드의 각 카메라가 부모, 자신, 직계 자식 노드를 모니터링 할 수 있는 트리 노드에 카메라를 설치한다. 트리의 모든 노드를 모니터링 하는데 필요한 최소 카메라 수를 구하라. DFS로 최하단에 있는 노드들부터 상태를 갱신하면서 탐색한다. 각 노드들에서 나타날 수 있는 경우는 총 3가지이다. 1. Not Monitored : 모니터링 되고 있지 않은 상태이다. (이 경우 부모 노드에서 처리하도록 한다.) 2. Monitored : 모니터링 되고 있는 상태이다. 3. Set Camera : 카메라가 세팅된 상태이다. 탐색 중인 노드는 초기 값은 모니터링 되고 있지 않은 상태(.. 2022. 6. 17. [Leetcode] 1658. Minimum Operations to Reduce X to Zero 문제 : https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ 정수 배열 nums와 정수 x가 입력으로 주어진다. 한 번의 작업으로 배열 nums에서 가장 좌측 혹은 가장 우측에 있는 요소를 제거 하고 x에서 제거한 요소의 값을 뺄 수 있다. 최소 몇 번의 작업으로 x를 정확히 0으로 만들 수 있는지 구하라. 만일 불가능하다면 -1을 반환하라. 부분합과 투포인터로 구할 수 있다. 부분합을 만들어 subsum 배열에 세팅한다. 첫 번째 예제 [1, 1, 4, 2, 3], x=5 로 표를 세팅해보면 [그림1]과 같다. 정답이 되는 제거되는 요소는 가장 뒤 요소 2, 3이다. 이를 반대로 생각하면 제거되지 않는 요소들의 합은 nums 전체.. 2022. 6. 11. [Leetcode] 785. Is Graph Bipartite? 문제 : https://leetcode.com/problems/is-graph-bipartite/ 인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다. 인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다. 인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다. 시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다. 모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배.. 2022. 4. 29. 이전 1 2 3 4 5 6 ··· 29 다음
