3524. Find X Value of Array I
배열 앞뒤를 잘라내고 남은 부분의 곱을 k로 나눈 나머지별로 경우의 수를 세는 문제. 문제가 prefix, suffix를 떼는 식으로 되어 있어서 처음엔 잘 안 보였는데, 결국 남는 건 비어있지 않은 부분 배열 하나다. 즉 모든 부분 배열의 곱 % k를 세는 문제. 처음엔 prefix sum처럼 prefix product로 구간 곱을 꺼내려고 했는데 안 된…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 81
324 322 1401. Circle and Rectangle Overlapping
원과 축에 나란한 직사각형이 겹치는지 판정하는 문제. 일단 좌표 범위가 작아서 테두리의 정수 점을 전부 돌려봤다. 입력이 전부 정수라 가장 가까운 점도 정수라서 이걸로도 통과는 된다. 근데 그럴 필요가 없다. 원 중심에서 가장 가까운 직사각형 위의 점 하나만 보면 되고, 그 점은 좌표를 구간에 자른 (min(max(x1, xCenter), x2), min(…
320 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
합이 target인 겹치지 않는 부분 배열 두 개를 골라서 길이의 합을 최소로 만드는 문제. 일단 arr[i] >= 1이라 전부 양수다. 그래서 합이 target인 구간은 슬라이딩 윈도우로 죽 밀면서 찾아주면 된다. 겹치지 않게 두 개를 고르는 게 문제인데, 오른쪽 구간을 고정하면 왼쪽은 제일 짧은 것 하나만 알면 된다. minLen[i]를 i 이하에서 끝…
319 1621. Number of Sets of K Non-Overlapping Line Segments
1차원 위에 놓인 점 n개에서 서로 겹치지 않는 선분 k개를 그리는 경우의 수를 구하는 문제. 선분은 점을 둘 이상 덮어야 하고 끝점은 공유할 수 있다. modular 나온 걸 보고 딱 DP겠거니 했다. 어제 2472처럼 겹치지 않게 k개를 고르는 문제인데 이번엔 최대 개수가 아니라 경우의 수다. 한 점에서 할 수 있는 건 이어붙이기, 끊고 넘어가기, 새로…
316 2265. Count Nodes Equal to Average of Subtree
이진 트리에서 자기 값이 서브트리 전체 값의 평균(내림)과 같은 노드의 개수를 구하는 문제. 노드마다 서브트리를 다시 돌면 O(n^2)이다. 평균을 구하려면 서브트리의 합과 개수만 있으면 되고, 둘 다 자식 값으로 바로 구할 수 있다. 즉, 후위 순회로 (합, 개수)를 올려주면 한 번만 돌아도 된다. 정답 개수도 같은 튜플에 넣어서 올려주면 따로 변수가 필…
315 835. Image Overlap
n x n 이진 행렬 img1을 상하좌우로만 평행이동해서 img2 위에 겹쳤을 때, 둘 다 1인 칸의 최대 개수를 구하는 문제. n이 최대 30이라 평행이동을 전부 해봐도 (2n-1)^2 = 3481번이다. 그냥 다 돌려보면 된다. 처음에는 (3n-1) x (3n-1) 보드를 깔고 img1을 실제로 옮겨 그려서 셌는데 시간 초과가 났다. 이동할 때마다 보드…
313 3871. Count Commas in Range II
1부터 n까지의 수를 세 자리마다 콤마를 찍어서 쓸 때, 콤마가 총 몇 개 쓰이는지 구하는 문제. n이 10^15까지라 하나씩 세는 건 불가능하다. 잘 생각해보면 1000 이상인 수는 콤마가 최소 1개, 10^6 이상이면 최소 2개... 이런 식이다. 즉, 1000의 거듭제곱마다 그 이상인 수의 개수를 더해주면 된다. n 이하에서 div 이상인 수는 n -…
312 2461. Maximum Sum of Distinct Subarrays With Length K
k 길이의 부분 배열 중에 원소가 전부 다를 때의 합의 최댓값을 구하는 문제 간단한 슬라이딩 윈도우 문제. 원소 하나씩 보면서 counter 하면서 모두 distinct 이면 결과에 업데이트 해주면 된다.
311 129. Sum Root to Leaf Numbers
루트부터 리프 노드까지를 이었을 때 생기는 수를 다 더하는 문제 재귀적으로 구현하면 된다. 자식 노드로 내려갈 때 현재 값에 10을 계속 곱해주면서 더하면 된다. 보통 재귀적으로 합을 구할 때와 순서가 반대라서 약간 헷갈리긴 한다
310 103. Binary Tree Zigzag Level Order Traversal
이진 트리가 주어질 때 레벨 별로 지그재그 하면서 출력하는 문제 레벨별로 맵을 만들고 순서에 맞게 집어넣으면 된다. 일반 bfs 탐색을 약간 변형하면 됨