763. Partition Labels
문자열을 각 문자들이 최대 한 덩어리에만 있도록 나눠야 한다. 최대한 많이 나눌 때의 덩어리 개수를 구하는 문제. 잘 생각해보면 한 덩어리에만 있어야 한다는 것은 다음 덩어리에는 해당 문자가 나타나서는 안 된다는 것이다. 다음 문자가 어디 있는지 map을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다. 위…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 81
204 201 1249. Minimum Remove to Make Valid Parentheses
올바른 괄호 문자열이 되도록 최소한의 문자를 제거하는 문제. 최소한을 제거해야 하므로 제거할 필요가 없는 애들은 놔둬야 한다. 즉, 올바른 괄호면 제거하지 않고 올바르지 않은 괄호만 골라서 지우면 된다. 간단한 카운터를 하나 두고 (가 나오면 ++, )가 나오면 --로 해서 올바른지 판단할 수 있다. 이렇게 하면 열지 않았는데 닫는 괄호를 제거해줄 수 있고…
198 61. Rotate List
링크드 리스트를 k번 회전시키는 문제. 그냥 말 그대로 k번 회전시키면 된다. k가 크므로 먼저 리스트의 길이를 구해서 mod 연산으로 줄여줘야 하고, 회전 후 맨 뒤로 이동해서 연결을 끊어준 후 끊어진 tail과 head를 연결하면 된다.
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