517. Super Washing Machines
세탁기에 옷들이 있고 옷들을 한번에 하나씩 이동시킬 수 있을 때 모든 옷의 개수가 같게 만드는 최소 이동 횟수를 구하는 문제. 일단 전체 합이 개수의 배수가 되어야 하니 먼저 예외 처리를 해주고, 모든 세탁기의 옷은 합 / 개수가 되어야 한다. 여기서 간단하게 드는 생각은 가장 큰 값 - (합 / 개수) 하면 답일까? 싶은데 반례가 존재한다. [0,0,2,…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
281 280 279 2. Add Two Numbers
링크드 리스트 형태로 수가 2개 주어질 때 더한 값을 링크드 리스트로 출력하는 문제. 자리수는 계산하기 쉽게 반대로 되어 있다. 간단한 링크드 리스트 구현 문제. 그냥 자리수대로 한 칸 씩 앞으로 가면서 더해주면 된다.
278 3016. Minimum Number of Pushes to Type Word II
주어진 문자열을 키패드로 입력할 때 버튼 누르는 횟수의 최소를 구하는 문제. 키패드는 자유롭게 배치할 수 있다. 간단한 문제. 문자열의 문자들의 개수를 센 뒤, 개수가 많은 문자를 키패드의 앞쪽으로 배치하면 된다.
277 2134. Minimum Swaps to Group All 1's Together II
1을 임의의 0과 swap해서 1이 연속되게 만드는 문제. 단, 배열은 원형이다 한 덩어리로 만든다고 생각해보면 1이 나온 개수만큼 어딘가에 뭉쳐놓는다고 볼 수 있다. 그렇게 되면 슬라이딩 윈도우 방법으로 1이 나온 개수 크기의 윈도우로 배열을 순회하면서 그 윈도우 안의 0의 개수가 swap 횟수가 된다. 원형 처리는 간단하게 배열을 그냥 뒤에 그대로 붙여…
276 2053. Kth Distinct String in an Array
문자열의 배열이 주어질 때 k번째 distinct한 문자열을 찾는 문제 그냥 Counter로 개수 세고 1개인 애들 중 k번째를 리턴하면 된다. easy 문제 풀면 자괴감 드네... (오늘의 문제니깐 푼다... ㅋㅋ)
275 1508. Range Sum of Sorted Subarray Sums
모든 subarray의 합을 정렬한 후 left부터 right 까지 합을 구하는 문제 그냥 문제 그대로 모든 subarray에 대해 합을 구한 후 정렬하면 된다. 당연하게도 합을 구할 때는 prefix sum으로 구해야 시간 안에 들어온다. 시간 복잡도는 정렬 때문에 O(n^2 log(n^2)) sliding window, binary search를 쓰면 …
274 801. Minimum Swaps To Make Sequences Increasing
nums1, nums2 배열의 같은 위치의 원소를 swap 해서 배열을 증가하게 만드는 (strictly increasing) 최소 swap 횟수를 구하는 문제. 현재 인덱스에서 swap 한다 / 안한다 두 가지를 할 수 있고 이를 dp로 풀 수 있다. swap 처리가 약간 까다롭긴 한데 swapped 변수에 따라 이전 인덱스 비교를 다르게 해서 풀 수 있…
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로 구현하면 된다.