1397. Find All Good Strings
사전순으로 s1 와 s2 사이의 n 길이 문자열 중에 evil 이 부분 문자열로 안 들어간 개수를 구하는 문제. 꽤나 어렵다. 참고함. 먼저 DP라는 건 modular 연산이나 감으로 알 수 있다. s1, s2 사이의 문자열의 개수를 DP로 구현할 수 있다. 문제는 evil 문자열을 걸러내는 건데... KMP 알고리즘을 사용하면 된다. KMP 는 로이형의 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
hard 69
188 187 336. Palindrome Pairs
문자열들이 주어질 때 팰린드롬이 되는 페어를 전부 구하는 문제. 단순 완전 탐색을 하면 시간 초과가 된다. 살짝 고민하면 문자열이 팰린드롬이 되도록 하는 다른 문자열을 찾는 방법을 생각해볼 수 있다. 즉, 문자열을 left, right로 나눴을 때 right가 팰린드롬이면 left의 역순을 오른쪽에 붙인 문자열이 팰린드롬이 될 것이다. 비슷하게 left가 …
186 174. Dungeon Game
2차원 던전이 있고 가장 오른쪽 아래의 공주를 구해야 한다. 각 배열의 값에 해당하는 만큼의 체력이 깎이거나 증가될 때, 공주를 구하려면 필요한 최소의 체력을 구하는 문제. 전형적인 DP이다. 특히 거꾸로 올라가는 방향이 없을 경우 (이 문제에서는 오른쪽와 아래 방향으로만 갈 수 있다) 거의 DP로 풀 수 있다. 으로 정의하면 DP[x][y] = min(D…
184 765. Couples Holding Hands
커플이 2n개의 좌석을 서로 붙어 있게 앉기 위한 최소의 스왑 횟수를 구하는 문제. 그리디하게 생각하면 의외로 쉽게 풀린다. 일단 앞에서 순차로 탐색한다고 해보면 짝이 안 맞는 사람이 있을 경우 뒤쪽에서 한 명이랑 스왑을 해줘야 한다. 그리고 이렇게 스왑을 한 경우 이 커플은 더 이상 스왑을 해줄 필요가 없어진다. 이렇게 순차적으로 커플이 되도록 스왑을 쭉…
183 546. Remove Boxes
계속해서 연속된 수를 제거할 수 있고 제거한 개수의 제곱의 점수를 얻을 수 있다. 최대로 얻는 점수를 구하는 문제. 하드 중에서도 하드한 문제. 다른 사람의 풀이를 보고 풀긴 하였다. 일단 결론부터 말하면 3차원 DP 문제. 연속된 개수가 중요하므로 3차원으로 해야한다. dp[i][j][k] = i 부터 j 까지의 최대 점수, k는 i와 같은 지금까지의 연…
180 878. Nth Magical Number
a 또는 b로 나누어 지는 수를 magical number라 할 때, n번째 magical number를 구하는 문제 일단 n이 크니까 탐색 범위를 줄여보자 LCM을 쓰면 a, b에 동시에 나누어지는 수를 구할 수 있고 이를 이용해 자르면 된다. 자른 다음 나머지 n에 대해 하나씩 a, b를 더해가면서 n번째 수를 구할 수 있다. 솔루션을 보면 이진 탐색으…
174 85. Maximal Rectangle
2차원 배열에서 1로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제. 정사각형의 경우 간단한 DP로 가능한데 직사각형이므로 DP 풀이는 약간 복잡하다. 예전에 로이형 유튜브에서 보긴 해서 그 풀이로 가보기로 하자. 이전 문제인 84. Largest Rectangle in Histogram 문제를 응용하면 된다. 각 칸을 히스토그램의 칸이라 생각하고 아래…
173 224. Basic Calculator
괄호, +, - 가 있는 간단한 계산기를 만드는 문제. 스택으로 하면 될 것 같다. 기본 기호 (+, -) 가 나오면 스택에 집어넣고, 괄호가 나오면 새로 스택을 쌓아주고 괄호가 닫히면 스택에서 하나를 더 빼주는 식으로 구현했다. 약간 코드가 지저분하지만 기본 흐름은 스택을 쓰는 것이다.
172 149. Max Points on a Line
같은 직선에 있는 점의 최대 개수를 구하는 문제. 인풋 범위가 300개로 매우 작아서 그냥 다 돌려보면 된다. 심지어 x, y 범위도 작아서 (-10000 ~ 10000) 단순 기울기로만 카운트를 해주면 된다. 단, x, y 범위가 크다면 부동소수점 오차로 인해 gcd를 이용해서 기울기가 같은 점을 더해줘야 한다.
171 315. Count of Smaller Numbers After Self
배열에서 자신보다 뒤에 작은 수가 몇 개 나오는지 출력하는 문제. 처음엔 응?했지만 계속 보니 범위 문제라는 것이 보인다. 레드블랙트리에서 lower_bound 하거나 펜윅 트리를 쓰면 될 것 같다. 단, 레드 블랙 트리에서 lower_bound는 C++만 되는 것 같으니 간단한 펜윅 트리를 구현해보자. 위 링크에서 간략하게 핵심을 잘 정리해 놓았다. 범위…