959. Regions Cut By Slashes
슬래시로 나뉜 영역의 개수를 세는 문제. 원본 그리드에서 개수를 세는건 꽤 복잡하다. 그래서 크기를 키운 3x3 그리드에서 영역의 개수를 셀 수 있다. 출처: 에디토리얼 시간복잡도는 O(n^2) 나는 처음에 4x4로 풀었는데 잘 생각해보니 2x2로도 될 것 같다. 원본 그리드를 참고해서 / 이면 대각선으로 1,3분면을 이동 가능하게 하고 \이면 2,4분면을…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
290 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으로 나눠야만 한다.
284 1492. The kth Factor of n
n의 약수 중 k번째 작은 수를 찾는 문제 그냥 모든 약수를 구하고 정렬 후 k번째를 찾으면 된다. 정렬해도 O(n) 이하긴 한데 (O(sqrt(n) log sqrt(n))) 정렬 없이 풀 수 있다. 약수 저장 배열을 2개 두면 된다. 약수를 구할 때 d가 약수이면 배열에 d를 넣고 다른 배열은 n/d를 집어넣으면 각 배열은 정렬이 되어있는 상태이고 k번째…
283 273. Integer to English Words
숫자를 영어로 변환하는 문제. 문제는 매우 쉽지만 아주 지저분하다. 1000씩 끊고 10씩 끊는 등 숫자를 잘게 나누면 그나마 덜 지저분하게 짤 수 있다. 오타 조심..! (Ninety 잘못 쳐서 1번 틀림..)
282 312. Burst Balloons
풍선을 터뜨릴 때 최대 점수를 구하는 문제. 터뜨릴 때는 풍선의 양쪽과 현재 값을 곱한 값이 점수가 된다. 딱 보면 해답이 나오지 않는 DP 문제. 문제를 반대로 생각해봐야 한다. 일단 문제 그대로는 이전 선택이 이후 선택에 영향을 주기 때문에 DP를 적용하기 어렵다. 다만, 풍선을 먼저 터뜨릴 것을 고르는 것이 아니고 마지막에 터뜨릴 것을 고른다고 생각하…
281 517. Super Washing Machines
세탁기에 옷들이 있고 옷들을 한번에 하나씩 이동시킬 수 있을 때 모든 옷의 개수가 같게 만드는 최소 이동 횟수를 구하는 문제. 일단 전체 합이 개수의 배수가 되어야 하니 먼저 예외 처리를 해주고, 모든 세탁기의 옷은 합 / 개수가 되어야 한다. 여기서 간단하게 드는 생각은 가장 큰 값 - (합 / 개수) 하면 답일까? 싶은데 반례가 존재한다. [0,0,2,…