본문 바로가기

greedy27

[Leetcode] 1996. The Number of Weak Characters in the Game 문제 : https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/ 정렬 후, 그리디로 풀었다. 앞에서부터 탐색하면서 탐색중인 요소가 정답이 될 수 있는지 판단해야 한다. 공격, 방어 둘 다가 작아야 하므로. 먼저 공격을 내림차순으로 정렬한다. 공격은 내림차순 정렬했기 때문에 이때동안 탐색했던 모든 요소들의 공격은 현재 탐색하는 요소의 공격보다 크거나 같다(1). 따라서, 현재 탐색중인 방어보다 큰 값이 이때까지 탐색했던 방어들 값 중 있는지만 판단하면 된다. 큰 값을 구해야 하므로 탐색 중에 방어 값들 중 최대 값을 변수(maxDepen)에 저장해두고 이를 비교하면 O(1)만에 비교가능하다. 문제에서 공격, 방어를 비교할 때 str.. 2022. 9. 9.
[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] 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] 630. Course Schedule III 문제 : https://leetcode.com/problems/course-schedule-iii/ 소요기간(연속), 완료되어야 하는 기간을 가진 course들의 배열 courses이 입력으로 주어진다. 1일차부터 시작하고 2개의 코스를 한 번에 들을 수는 없다. 수강할 수 있는 최대 코스 수를 구하라. courses 배열을 완료되어야 하는 기간의 오름차순으로 정렬한다. 우선순위큐를 만든다. 이 큐에는 현재까지 수강가능한 최대 코스 수를 가지는 코스들의 수강기간(duration)로 이루어져 있다. (왜 duration을 넣는지는 뒤에서 설명할 예정(1)) 큐에 있는 코스들을 모두 수강했을 때 쇼요기간을 day 변수에 저장해둔다. 정렬된 courses 배열을 앞에서부터 탐색하면서 큐에 넣을 수 있는지 판단.. 2022. 6. 24.
[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] 1526. Minimum Number of Increments on Subarrays to Form a Target Array 문제 : https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/ 양의 정수 배열 target과 동일한 크기의 초기값이 모두 0인 initial 배열이 있다. 한 번의 연산에서 initial 배열의 하위배열의 요소값들을 1씩 증가시킬 때, initial 배열에서 target 배열로 만들 수 있는 최소 연산 횟수를 구하라. 결국은 어느 부분을 하위 배열로 묶을 것인지를 찾는게 중요하다. target 배열을 앞에서부터 탐색하면서 이전 값 보다 탐색 중인 값이 더 큰 경우 이전 값과의 차이(하위 배열을 제외하고 추가로 증가되어야 하는 수)를 정답에 더해준다. 탐색하는 값이 이전 값보다 같거나 작다.. 2021. 11. 30.