40. Combination Sum II
배열과 수가 주어질 때 합이 수가 되도록 만드는 배열의 조합을 모두 구하는 문제. n=100이라 힘들것 같지만 완전탐색으로 풀린다. 일단 target의 범위도 작고, 중복을 제외하는 등 가지치기가 꽤 된다. 반대로 말하면 가지치기를 못하면 시간초과가 난다. 중복을 제거하기 위해 일단 정렬. 한 탐색 내에서 같은 원소는 건너뛰는 방식으로 돌려야 한다. 예를 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
293 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 279 2. Add Two Numbers
링크드 리스트 형태로 수가 2개 주어질 때 더한 값을 링크드 리스트로 출력하는 문제. 자리수는 계산하기 쉽게 반대로 되어 있다. 간단한 링크드 리스트 구현 문제. 그냥 자리수대로 한 칸 씩 앞으로 가면서 더해주면 된다.
278 3016. Minimum Number of Pushes to Type Word II
주어진 문자열을 키패드로 입력할 때 버튼 누르는 횟수의 최소를 구하는 문제. 키패드는 자유롭게 배치할 수 있다. 간단한 문제. 문자열의 문자들의 개수를 센 뒤, 개수가 많은 문자를 키패드의 앞쪽으로 배치하면 된다.