1140. Stone Game II
돌들이 있고 Alice와 Bob이 차례로 돌을 가져갈 때 최대가 되게 가져가는 점수를 구하는 문제. 1 - 2*M개의 돌을 가져갈 수 있다. 이런 게임류 문제가 익숙하지 않으면 꽤 어렵다. 이렇게 두면 좀 보일까 싶은데 쉽지 않다. 여기서 Alice와 Bob의 관계를 생각해봐야 하는데 Alice는 Bob이 최소로 가져가게 골라야 한다. 그럼 Alice가 가…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
300 299 650. 2 Keys Keyboard
복사, 붙여넣기만 가능한 키보드에서 특정 길이를 만드는 최소 횟수를 구하는 문제 일단 간단히 DP로 풀리긴 한다. dp[i][j] = i길이를 j만큼 붙여넣어 만들때 최소 횟수. O(n^2) 그런데 여기서 수학적으로 접근하면 O(n)으로 가능하다. 자세한건 에디토리얼 참고.
298 264. Ugly Number II
소인수가 2, 3, 5로만 이루어진 수를 ugly number라 할 때 n번째 ugly number를 구하는 문제 n범위가 작아서 무식하게 구해도 통과는 된다. 좀 더 O(n)으로 잘 구해볼 수 있을까.. 약간의 dp를 쓸 수 있다. 일단 다음 수는 이전의 ugly number들 뒤에 2, 3, 5를 곱한 수가 된다. 그 중 제일 작은 수가 다음 수가 된다…
297 1937. Maximum Number of Points with Cost
2차원에서 점수를 먹는 문제. 먹을 때 이전에 먹은 열과 비교해서 그 차이만큼은 빼야 한다. 3차원 dp는 쉽다. 다만 시간 초과. 2차원으로 어떻게 하면 줄일 수 있을까? 왼쪽에서 왔을 때의 최대와 오른쪽에서 왔을 때의 최대를 같이 구해서 그 중 최대값으로 업데이트하면 된다. 에디토리얼 참고. 간단하게 설명하면 left_max[i]는 i보다 왼쪽의 점수 …
296 624. Maximum Distance in Arrays
배열이 여러개 주어질 때 서로 다른 배열끼리 가장 큰 원소의 차이를 출력하는 문제. 그리디? 라고도 볼 수 있다. 일단 차가 가장 크려면 각각 다른 배열의 최대와 최소를 빼줘야 한다. 중간에 있는 원소는 필요 없다. 간단하고 직관적으로 짜려면 모든 배열의 최대와 최소를 구한 뒤 같은 배열이라면 두번째 최대 혹은 두번째 최소로 답을 구할 수 있긴 하다. 힙으…
295 860. Lemonade Change
5달러로 레모네이드를 팔 때 거스름돈을 줄 수 있는지 판단하는 문제. 손님은 5, 10, 20 달러 지폐만 사용한다. 그냥 단순 시뮬레이션. 약간의 그리디도 들어가는데 20달러를 냈을 때 10달러가 있다면 10달러 포함해서 거슬러 주는게 무조건 이득이다. 나머지는 5달러로 거슬러 주고 5달러 지폐가 음수가 되면 False를 리턴하면 된다.
294 719. Find K-th Smallest Pair Distance
배열 중에서 pair의 차이가 k번째로 작은 값을 찾는 문제 대충 감으로 이진 탐색으로 찾아야할 것 같다. 그런데 어떻게 n보다 작은 pair 개수를 셀 수 있을까? 슬라이딩 윈도우로 셀 수 있다. 먼저 배열을 정렬해주자. 그 후 n보다 작은 pair의 개수를 세는 함수를 정의하고 n을 이진 탐색으로 돌면서 k개가 나올 때까지 탐색해주면 된다. n보다 작은…
293 40. Combination Sum II
배열과 수가 주어질 때 합이 수가 되도록 만드는 배열의 조합을 모두 구하는 문제. n=100이라 힘들것 같지만 완전탐색으로 풀린다. 일단 target의 범위도 작고, 중복을 제외하는 등 가지치기가 꽤 된다. 반대로 말하면 가지치기를 못하면 시간초과가 난다. 중복을 제거하기 위해 일단 정렬. 한 탐색 내에서 같은 원소는 건너뛰는 방식으로 돌려야 한다. 예를 …
292 703. Kth Largest Element in a Stream
stream이 주어질 때 순서대로 k번째로 큰 수를 출력하는 문제 min heap으로 간단히 구현할 수 있다. 처음에는 heap 2개를 썼는데 k개만 관리하면 돼서 k 길이의 min heap 하나면 충분하다. k 길이의 min heap을 관리하면서 min heap에서 가장 작은 값보다 큰 값이 들어오면 min heap에서 빼고 갱신해주면 된다.
291 1568. Minimum Number of Days to Disconnect Island
2d 배열로 맵이 주어진다. 0은 바다, 1은 육지. 1을 0으로 바꿔서 섬이 2개로 나눌 수 있는 최소 횟수를 구하는 문제. 엄청 어려워 보이는데 간단하게 풀 수 있는 방법이 있다. 답은 무조건 0, 1, 2 중 하나이다. 일단 0, 1은 그럴 수 있는데 왜 2번만에 모든 섬을 2개로 나눌 수 있을까? 섬이 어떻게 생겼든 꼭지점을 나눠서 섬을 2개로 만들…