1937. Maximum Number of Points with Cost
2차원에서 점수를 먹는 문제. 먹을 때 이전에 먹은 열과 비교해서 그 차이만큼은 빼야 한다. 3차원 dp는 쉽다. 다만 시간 초과. 2차원으로 어떻게 하면 줄일 수 있을까? 왼쪽에서 왔을 때의 최대와 오른쪽에서 왔을 때의 최대를 같이 구해서 그 중 최대값으로 업데이트하면 된다. 에디토리얼 참고. 간단하게 설명하면 left_max[i]는 i보다 왼쪽의 점수 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 81
297 296 624. Maximum Distance in Arrays
배열이 여러개 주어질 때 서로 다른 배열끼리 가장 큰 원소의 차이를 출력하는 문제. 그리디? 라고도 볼 수 있다. 일단 차가 가장 크려면 각각 다른 배열의 최대와 최소를 빼줘야 한다. 중간에 있는 원소는 필요 없다. 간단하고 직관적으로 짜려면 모든 배열의 최대와 최소를 구한 뒤 같은 배열이라면 두번째 최대 혹은 두번째 최소로 답을 구할 수 있긴 하다. 힙으…
293 40. Combination Sum II
배열과 수가 주어질 때 합이 수가 되도록 만드는 배열의 조합을 모두 구하는 문제. n=100이라 힘들것 같지만 완전탐색으로 풀린다. 일단 target의 범위도 작고, 중복을 제외하는 등 가지치기가 꽤 된다. 반대로 말하면 가지치기를 못하면 시간초과가 난다. 중복을 제거하기 위해 일단 정렬. 한 탐색 내에서 같은 원소는 건너뛰는 방식으로 돌려야 한다. 예를 …
290 959. Regions Cut By Slashes
슬래시로 나뉜 영역의 개수를 세는 문제. 원본 그리드에서 개수를 세는건 꽤 복잡하다. 그래서 크기를 키운 3x3 그리드에서 영역의 개수를 셀 수 있다. 출처: 에디토리얼 시간복잡도는 O(n^2) 나는 처음에 4x4로 풀었는데 잘 생각해보니 2x2로도 될 것 같다. 원본 그리드를 참고해서 / 이면 대각선으로 1,3분면을 이동 가능하게 하고 \이면 2,4분면을…
289 840. Magic Squares In Grid
2d 그리드가 주어질 때 안에서 magic square가 되는 부분 그리드의 개수를 구하는 문제. 그냥 돌려주면 된다. 1-9까지의 distinct가 나와야 되고 가로, 세로, 대각선의 합이 다 같은지 확인한다. magic square의 특성을 잘 분석해보면 간단하게 풀 수 있다. 일단 행, 열, 대각선을 더해서 다 같으려면 15가 나와야 한다. 그리고 적…
288 930. Binary Subarrays With Sum
부분 배열 중 합이 goal인 개수를 출력하는 문제 뭔가 슬라이딩 윈도우로 되지 않을까 했는데 쉽지 않다. 가능하긴 한데 0 prefix 개수를 관리하거나 (1 pass) 최대 k인 개수를 구한 다음 최대 k-1인 개수를 빼서 구하거나 (2 pass)... 에디토리얼 참고. prefix sum을 쓰면 쉽게 풀린다. 지금까지의 합이 나온 수를 카운트 하면서 …
286 885. Spiral Matrix III
지정된 위치에서 배열을 spiral (달팽이) 모양으로 순회할 때 위치를 출력하는 문제. 일단 나는 202 x 202의 가상 보드를 만들고 무식하게 달팽이를 만들었다... (사람이 보고 적는 것처럼 수가 없으면 앞으로 가고 있으면 방향을 트는 방식). 시간복잡도는 O(RC) 그런데 달팽이 만들 때의 규칙을 쓰면 더 간단하게 풀 수 있다. 달팽이 만들 때는 …
285 2405. Optimal Partition of String
문자열을 겹치는 문자 없는 substring으로 나눌 때 최소 횟수를 구하는 문제. 그리디 적으로 생각하면 바로 풀린다. 문자열을 최대한 크게 나눈다고 생각하면 된다. 그런 다음 나눌 수밖에 없는 부분을 나눈다. 즉, 이미 나온 문자가 나타나면 새로운 substring으로 나눠야만 한다.
284 1492. The kth Factor of n
n의 약수 중 k번째 작은 수를 찾는 문제 그냥 모든 약수를 구하고 정렬 후 k번째를 찾으면 된다. 정렬해도 O(n) 이하긴 한데 (O(sqrt(n) log sqrt(n))) 정렬 없이 풀 수 있다. 약수 저장 배열을 2개 두면 된다. 약수를 구할 때 d가 약수이면 배열에 d를 넣고 다른 배열은 n/d를 집어넣으면 각 배열은 정렬이 되어있는 상태이고 k번째…
280