214. Shortest Palindrome
주어진 문자열이 팰린드롬이 되도록 문자열을 앞에 붙이는 문제. 처음에는 단순 while 루프를 돌았지만 예외가 발생함. 결국 KMP로 해결 KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 이용하면 팰린드롬을 구할 수 있다. 주어진 문자열에 뒤집은 문자열을 붙였을 때 prefix와 suffix가 같다는 것은 팰린드롬이…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
191 190 834. Sum of Distances in Tree
트리가 주어질 때 각 노드에서 다른 노드까지의 거리의 합을 모두 구하는 문제. 단순 N^2은 시간 초과이므로 한 번(N)에 구해야 한다. 잘 생각해보면 각 노드의 자식 노드의 개수를 이용하면 된다. 먼저 0번 노드부터 다른 노드까지의 거리를 구해준 다음, 각 노드에서 거리를 구할 땐 자식 노드의 개수를 이용하면 된다. 거리를 계산할 기준 노드를 child로…
189 1857. Largest Color Value in a Directed Graph
노드에 색이 칠해져 있는 방향 그래프가 주어진다. 그래프의 path 중 가장 많이 나온 색깔의 개수를 구하는 문제. 사이클이 있다면 -1을 출력. 처음엔 dfs로 구현해서 제출했는데 엣지 케이스 처리가 까다롭다. (사이클 탐지, visited 체크 등) 결국 위상 정렬로 다시 제출. 그리디적인 방법을 생각해보면 가장 색깔이 많이 나오려면 경로의 제일 처음부…
188 1397. Find All Good Strings
사전순으로 s1 와 s2 사이의 n 길이 문자열 중에 evil 이 부분 문자열로 안 들어간 개수를 구하는 문제. 꽤나 어렵다. 참고함. 먼저 DP라는 건 modular 연산이나 감으로 알 수 있다. s1, s2 사이의 문자열의 개수를 DP로 구현할 수 있다. 문제는 evil 문자열을 걸러내는 건데... KMP 알고리즘을 사용하면 된다. KMP 는 로이형의 …
187 336. Palindrome Pairs
문자열들이 주어질 때 팰린드롬이 되는 페어를 전부 구하는 문제. 단순 완전 탐색을 하면 시간 초과가 된다. 살짝 고민하면 문자열이 팰린드롬이 되도록 하는 다른 문자열을 찾는 방법을 생각해볼 수 있다. 즉, 문자열을 left, right로 나눴을 때 right가 팰린드롬이면 left의 역순을 오른쪽에 붙인 문자열이 팰린드롬이 될 것이다. 비슷하게 left가 …
186 174. Dungeon Game
2차원 던전이 있고 가장 오른쪽 아래의 공주를 구해야 한다. 각 배열의 값에 해당하는 만큼의 체력이 깎이거나 증가될 때, 공주를 구하려면 필요한 최소의 체력을 구하는 문제. 전형적인 DP이다. 특히 거꾸로 올라가는 방향이 없을 경우 (이 문제에서는 오른쪽와 아래 방향으로만 갈 수 있다) 거의 DP로 풀 수 있다. 으로 정의하면 DP[x][y] = min(D…
185 152. Maximum Product Subarray
배열에서 subarray 곱 중 가장 최댓값을 구하는 문제 곱할 때 핵심은 현재까지 최댓값에 -를 곱하게 되면 최소가 되고 -를 더 곱하게 되면 다시 최대가 된다는 점이다. 즉 최대 최소가 번갈아가며 나올 수 있다는 것이다. 여기에서 maxim, minim 으로 최대, 최소를 다 선언해두고 계속 갱신해주면 된다.
184 765. Couples Holding Hands
커플이 2n개의 좌석을 서로 붙어 있게 앉기 위한 최소의 스왑 횟수를 구하는 문제. 그리디하게 생각하면 의외로 쉽게 풀린다. 일단 앞에서 순차로 탐색한다고 해보면 짝이 안 맞는 사람이 있을 경우 뒤쪽에서 한 명이랑 스왑을 해줘야 한다. 그리고 이렇게 스왑을 한 경우 이 커플은 더 이상 스왑을 해줄 필요가 없어진다. 이렇게 순차적으로 커플이 되도록 스왑을 쭉…
183 546. Remove Boxes
계속해서 연속된 수를 제거할 수 있고 제거한 개수의 제곱의 점수를 얻을 수 있다. 최대로 얻는 점수를 구하는 문제. 하드 중에서도 하드한 문제. 다른 사람의 풀이를 보고 풀긴 하였다. 일단 결론부터 말하면 3차원 DP 문제. 연속된 개수가 중요하므로 3차원으로 해야한다. dp[i][j][k] = i 부터 j 까지의 최대 점수, k는 i와 같은 지금까지의 연…
182 1446. Consecutive Characters
연속된 문자 중 가장 긴 길이를 구하는 문제. 그냥 돌면서 구하면 된다... 이걸 글로 써야 하나 고민했지만 푼 문제니까 그냥 올리기로 결정.