2. Add Two Numbers
링크드 리스트 형태로 수가 2개 주어질 때 더한 값을 링크드 리스트로 출력하는 문제. 자리수는 계산하기 쉽게 반대로 되어 있다. 간단한 링크드 리스트 구현 문제. 그냥 자리수대로 한 칸 씩 앞으로 가면서 더해주면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 81
279 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 횟수가 된다. 원형 처리는 간단하게 배열을 그냥 뒤에 그대로 붙여…
275 1508. Range Sum of Sorted Subarray Sums
모든 subarray의 합을 정렬한 후 left부터 right 까지 합을 구하는 문제 그냥 문제 그대로 모든 subarray에 대해 합을 구한 후 정렬하면 된다. 당연하게도 합을 구할 때는 prefix sum으로 구해야 시간 안에 들어온다. 시간 복잡도는 정렬 때문에 O(n^2 log(n^2)) sliding window, binary search를 쓰면 …
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이므로 중간을 기준으로 왼쪽은 더 작은 값, 오른쪽은 더 큰 값을 고르면 된다. 비슷하게 중간을 기준으로 왼쪽은 더 큰 값, 오른쪽은 더 작은 값을 갖는 배열의 개수를 구해서 더하면 정답이 …
264 912. Sort an Array
정렬 구현 문제 뭐 별거 없고 그냥 정렬을 구현하면 된다. nlogn 정렬들 중 아무거나 구현하면 되는데 제일 간단하면서 안정적인 merge sort를 구현하였다. 퀵 소트, 힙 소트 등 기억이 잘 안나네 ㅋㅋ
263 287. Find the Duplicate Number
배열에서 중복된 수를 찾는 문제. 단 배열의 조작은 불가능하고, 공간복잡도는 O(1)이어야 한다. 제약 조건이 없다면 매우 쉬운 문제... 하지만 제약 조건과 follow up을 전부 만족하려면 특별한 알고리즘이 필요하다. 일단 해당 문제를 링크드 리스트로 볼 수 있는데 nums의 값을 인덱스로 해서 다음 리스트로 넘어가는 링크드 리스트로 가정하면 링크드 …
262 57. Insert Interval
구간들이 주어질 때 새로운 구간을 추가하는 문제. 구간들은 겹칠 경우 머지되어야 한다. 약간 그리디 느낌? 겹치지 않은 경우는 그냥 결과 배열에 넣으면 되고 겹치는 경우는 left는 겹치는 구간들의 최소, right는 겹치는 구간들의 최대로 해서 추가하면 된다. 좀 지저분하게 짜긴 했지만 결과도 맞게 나오고 O(n)이라 별 상관 없다.