801. Minimum Swaps To Make Sequences Increasing
nums1, nums2 배열의 같은 위치의 원소를 swap 해서 배열을 증가하게 만드는 (strictly increasing) 최소 swap 횟수를 구하는 문제. 현재 인덱스에서 swap 한다 / 안한다 두 가지를 할 수 있고 이를 dp로 풀 수 있다. swap 처리가 약간 까다롭긴 한데 swapped 변수에 따라 이전 인덱스 비교를 다르게 해서 풀 수 있…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
274 273 1460. Make Two Arrays Equal by Reversing Subarrays
적당한 subarray를 골라서 swap했을 때 target 배열을 만들 수 있는지 체크하는 문제. 두 배열의 원소의 개수를 세서 같다면 만들 수 있다. 잘 생각해보면 버블 정렬 등 swap을 통해 어떠한 순서든 생성해낼 수 있다. swap의 횟수를 묻는 문제가 아니라 단순 True/False 문제이기 때문에 이런 식으로 간단하게 구할 수 있다. 비슷하게 …
272 1105. Filling Bookcase Shelves
책을 책장에 꽂아 넣을 때 높이가 최소가 되도록 꽂는 문제. DP 문제이다. 책을 꽂는 방식이 2가지가 있고 현재 shelf에 꽂을지 혹은 다음 shelf로 꽂을지 선택할 수 있다. 책의 너비가 전체 shelf 보다 크지 않으면 한 shelf로 다 꽂을 수 있다. 로 두고, 한 줄에 꽂을 수 있을 때까지 꽂으면서 top-down dp로 구현하면 된다.
271 1653. Minimum Deletions to Make String Balanced
a 또는 b를 최소한으로 지워서 문자열을 /a*b*/ 형태로 만드는 횟수를 구하는 문제. 기준점을 두고 그리디하게 왼쪽의 b를 지우고 오른쪽의 a를 지웠을 때 횟수의 합 중 최소를 구하면 된다. 마지막에 1 빼주는건 현재 위치가 중복으로 들어가서 그냥 빼주었다. (현재 위치도 카운트에 집어넣었기 때문) 또한, 배열을 안쓰고 count 변수 2개로도 풀 수 …
270 1395. Count Number of Teams
연속으로 작아지거나 커지는 3 크기의 부분 배열을 구하는 문제. 브루트 포스는 O(n^3)으로 불가. 약간 스마트한 브루트 포스로 풀린다. O(n^2) 배열의 크기가 3이므로 중간을 기준으로 왼쪽은 더 작은 값, 오른쪽은 더 큰 값을 고르면 된다. 비슷하게 중간을 기준으로 왼쪽은 더 큰 값, 오른쪽은 더 작은 값을 갖는 배열의 개수를 구해서 더하면 정답이 …
269 2045. Second Minimum Time to Reach Destination
신호등이 있는 그래프가 주어질 때 1부터 n으로 가는 경로 중에서 두번째로 짧은 경로를 구하는 문제. 일단 신호등이 change 마다 바뀌는데 다시 보면 시간이 change의 짝수 배이면 초록불, change의 홀수 배이면 빨간불이다. 이제 두번째로 짧은 경로를 구해야 하는데 마지막 도시에 두번째로 도착한 시간이 두번째로 짧은 경로가 된다. (가까운 순으로…
268 218. The Skyline Problem
빌딩이 주어질 때 스카이라인을 출력하는 문제. 상당히 빡센 문제이다. heap (pq)를 쓴다는 것을 알고 봐도 쉽지 않음. 일단 왼쪽부터 오른쪽으로 하나씩 스캔하는 방식으로 진행하면서 현재까지 겹쳐있는 빌딩의 높이를 관리해주면 풀 수 있다. 스캔은 빌딩 시작과 끝을 기준으로 해야 하므로 주어진 빌딩 배열을 분해해주자. 그리고 현재까지 빌딩 높이 관리는 가…
267 2551. Put Marbles in Bags
가방 안의 돌들을 k 그룹으로 묶을 때 최소 합과 최대 합의 차이를 구하는 문제. 처음에는 DP 느낌이지만 수가 너무 많다. 정답은 그리디로 가면 된다. 뭔가 정렬 느낌이긴 했는데 잘 안돼서 에디토리얼 참고함. 사진은 에디토리얼에서 가져옴 일단 시작 돌과 마지막 돌은 무조건 포함해야 하니 제외하자. 그러면 k-1번 가방의 돌들을 나누는 문제가 된다. 여기서…
266 514. Freedom Trail
ring와 입력해야 할 key가 주어질 때 최소 횟수로 ring을 돌려서 key를 만드는 횟수를 구하는 문제 간단한 DP로 풀 수 있다. 현재 위치 기준으로 왼쪽, 오른쪽으로 돌려가며 찾을 수 있다. 시간 복잡도는 O(R^2 K) left, right로 돌릴 때의 문자열을 찾을 때 전처리를 통해 미리 구해놓으면 더 빨리 구할 수 있다. 또는, 에디토리얼 보…
265 1289. Minimum Falling Path Sum II
행끼리 인접하지 않은 열의 수를 더해서 최소가 되도록 맨 아래까지 가는 합을 구하는 문제. O(n^3) 풀이는 매우 쉬운 DP. O(n^2) 풀이를 생각해보자. 그리디하게 생각해보면 된다. 다음 row로 넘어갈 때 col이 같지만 않으면 된다. 즉, col이 어떤 곳이라도 찍을 수 있다는 것. 이를 잘 이용하면 전체 스캔할 필요 없이 최솟값인 곳과 두번째 …