1542. Find Longest Awesome Substring
swap을 해서 팰린드롬이 될 수 있으면 awesome이라고 할 때, 주어진 문자열의 substring 중 가장 긴 awesome 부분 문자열의 길이를 구하는 문제. 일단 swap해서 팰린드롬이 되려면 문자의 수가 전부 짝수이거나 하나만 홀수이어야 한다. 그러면 각 문자가 나온 수를 카운트 해줘야 하는데... 이건 XOR 연산으로 해주면 된다. 각 문자의 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
194 193 2009. Minimum Number of Operations to Make Array Continuous
배열의 전체 원소들이 연속되게 만들 수 있게 원소의 수를 바꾸는 최소 횟수를 구하는 문제. 먼저 순서가 상관이 없으므로 정렬을 하고 시작하자. 그러면 뭔가 보이는데, 만약 결과 배열의 시작을 a 로 잡았다면 결과 배열은 [a, a+1, a+2 ... a + n-1] 이 된다. 여기서 힌트를 얻어 주어진 배열에서 임의의 원소를 시작으로 잡는 결과 배열을 얻을…
192 1411. Number of Ways to Paint N × 3 Grid
3개의 색을 사용해서 n x 3 크기의 그리드를 인접한 색이 같지 않도록 색칠하는 경우의 수를 구하는 문제. 딱 보니 DP이다. 색의 조합이 한정되어 있으므로 이를 배열로 넣어주고 DP를 돌리면 된다. 위 DP풀이는 O(n)이라 충분히 통과하지만 (정확히는 색의 조합 k, n * k * k) O(log n)으로도 가능한데... 행렬의 곱셈을 이용하면 된다!
191 214. Shortest Palindrome
주어진 문자열이 팰린드롬이 되도록 문자열을 앞에 붙이는 문제. 처음에는 단순 while 루프를 돌았지만 예외가 발생함. 결국 KMP로 해결 KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 이용하면 팰린드롬을 구할 수 있다. 주어진 문자열에 뒤집은 문자열을 붙였을 때 prefix와 suffix가 같다는 것은 팰린드롬이…
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 으로 최대, 최소를 다 선언해두고 계속 갱신해주면 된다.