본문 바로가기

HARD54

[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] 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] 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] 51. N-Queens 문제 : https://leetcode.com/problems/n-queens/ 두 개의 퀸이 서로 공격하지 않도록 n x n 체스판에 n개의 퀸을 배치하라. 가능한 모든 경우의 체스판 형태를 반환하라. (Q : 퀸, . : 빈칸) (참고로 퀸은 한 번 움직일 때 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동 가능) 백트래킹으로 풀었다. 퀸은 앞, 뒤, 옆, 대각선 방향을 원하는 만큼 이동 가능하기 때문에 row, col, 대각선에 놓을 수 있는지 여부를 저장해야 한다. 백트래킹 구현 시 하나의 행에 퀸을 두는 경우의 수를 판단한다고 하면 하나의 행에는 하나의 퀸만 놓게 구현하면 row 에 퀸을 놓을 수 있는지 여부는 저장을 하지 않아도 된다. 열의 퀸 저장가능 여부는 n 크기의 boolean .. 2022. 6. 4.
[leetcode] 354. Russian Doll Envelopes 문제 : https://leetcode.com/problems/russian-doll-envelopes/ 배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다. 정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다. 결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다. 위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다. [[4,5],[4,6],[6,7],[2,3],[1,1]] 입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다. height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려.. 2022. 5. 26.