61. Rotate List
링크드 리스트를 k번 회전시키는 문제. 그냥 말 그대로 k번 회전시키면 된다. k가 크므로 먼저 리스트의 길이를 구해서 mod 연산으로 줄여줘야 하고, 회전 후 맨 뒤로 이동해서 연결을 끊어준 후 끊어진 tail과 head를 연결하면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
198 197 138. Copy List with Random Pointer
랜덤 포인터가 있는 링크드 리스트를 그대로 복사하는 문제 죽 돌면서 복사하면 된다. 랜덤 포인터의 경우 map으로 random 노드를 관리해주면 된다.
185 152. Maximum Product Subarray
배열에서 subarray 곱 중 가장 최댓값을 구하는 문제 곱할 때 핵심은 현재까지 최댓값에 -를 곱하게 되면 최소가 되고 -를 더 곱하게 되면 다시 최대가 된다는 점이다. 즉 최대 최소가 번갈아가며 나올 수 있다는 것이다. 여기에서 maxim, minim 으로 최대, 최소를 다 선언해두고 계속 갱신해주면 된다.
181 416. Partition Equal Subset Sum
합이 같아지게 배열을 둘로 나눌 수 있는지 판단하는 문제. 처음엔 투포인터로 하다가 2, 2, 1, 1같은 케이스를 보고 dp로 풀었다. 핵심 아이디어는 합이 같아지게 나눈다는 것은 합이 배열의 전체 합의 절반이 되도록 만들 수 있는가를 판단하는 문제가 된다는 것이다. 이 아이디어로부터 배열의 각 원소를 더해보면서 합이 전체 합 / 2가 되는지 보면 된다.…
179 790. Domino and Tromino Tiling
2 * n 칸을 도미노와 트로미노 타일로 채울 수 있는 경우의 수를 구하는 문제. 전형적인 타일링 DP 문제. 1차원으로 되는 것 같은데 더 직관적인 2차원 배열로 풀었다. 그림으로 나타내면 이런 느낌이다. 그렇다면 점화식을 세울 수 있는데 dp[i][0] = dp[i - 2][0] + dp[i - 1][0] + dp[i - 1][1] dp[i][1] = …
178 1306. Jump Game III
배열의 인덱스 i에서 i + arr[i], i - arr[i]로 점프를 할 수 있을 때 0인 곳으로 갈 수 있는지 출력하는 문제. DFS / BFS로 돌려주면 되는데 BFS로 돌렸다.
176 337. House Robber III
이진 트리 상에서 연속하지 않은 노드의 합 중 최댓값을 구하는 문제. 딱 보니 간단한 DP이다. 현재 노드에서 훔치면 다음 자식 노드에서는 훔치면 안되고 현재 노드에서 훔치지 않았으면 자식 노드에서는 훔치거나 훔치지 않거나 2가지를 탐색하면 된다. 연속되지 않아야 하므로 이전의 상태가 필요하고 이도 같이 메모이제이션 해주면 된다. 파이썬은 간단하게 lru_…
175 162 1641. Count Sorted Vowel Strings
n 개의 모음을 이어 붙일 수 있다. 이때 사전 순으로 정렬된 문자열의 개수를 구하는 문제. 딱 보니 DP로 풀어야겠다는 생각이 든다. 로 두면 DP[i][j] = DP[i - 1][k] (0 <= k <= j)가 된다. 추가로 DP[i] 행은 계속 덮어 띄워지므로 1차원으로 줄일 수 있다. DP[j]: j번째 모음으로 시작하는 문자열의 개수