719. Find K-th Smallest Pair Distance
배열 중에서 pair의 차이가 k번째로 작은 값을 찾는 문제 대충 감으로 이진 탐색으로 찾아야할 것 같다. 그런데 어떻게 n보다 작은 pair 개수를 셀 수 있을까? 슬라이딩 윈도우로 셀 수 있다. 먼저 배열을 정렬해주자. 그 후 n보다 작은 pair의 개수를 세는 함수를 정의하고 n을 이진 탐색으로 돌면서 k개가 나올 때까지 탐색해주면 된다. n보다 작은…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
294 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개로 만들…
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을 쓰면 쉽게 풀린다. 지금까지의 합이 나온 수를 카운트 하면서 …
287 2392. Build a Matrix With Conditions
배열의 크기와 행과 열에서의 원소들의 순서가 주어질 때 순서에 맞게 배열을 만드는 문제. 간단한 위상정렬 문제. 원소들의 순서를 그래프로 보면 원소들의 놓는 순서는 위상 정렬로 쉽게 얻어낼 수 있다. 얻어낸 행와 열의 순서대로 배치하면 된다. 불가능한 경우, 사이클이 있다면 빈 배열을 리턴하면 된다.
286 885. Spiral Matrix III
지정된 위치에서 배열을 spiral (달팽이) 모양으로 순회할 때 위치를 출력하는 문제. 일단 나는 202 x 202의 가상 보드를 만들고 무식하게 달팽이를 만들었다... (사람이 보고 적는 것처럼 수가 없으면 앞으로 가고 있으면 방향을 트는 방식). 시간복잡도는 O(RC) 그런데 달팽이 만들 때의 규칙을 쓰면 더 간단하게 풀 수 있다. 달팽이 만들 때는 …
285 2405. Optimal Partition of String
문자열을 겹치는 문자 없는 substring으로 나눌 때 최소 횟수를 구하는 문제. 그리디 적으로 생각하면 바로 풀린다. 문자열을 최대한 크게 나눈다고 생각하면 된다. 그런 다음 나눌 수밖에 없는 부분을 나눈다. 즉, 이미 나온 문자가 나타나면 새로운 substring으로 나눠야만 한다.