3524. Find X Value of Array I
배열 앞뒤를 잘라내고 남은 부분의 곱을 k로 나눈 나머지별로 경우의 수를 세는 문제. 문제가 prefix, suffix를 떼는 식으로 되어 있어서 처음엔 잘 안 보였는데, 결국 남는 건 비어있지 않은 부분 배열 하나다. 즉 모든 부분 배열의 곱 % k를 세는 문제. 처음엔 prefix sum처럼 prefix product로 구간 곱을 꺼내려고 했는데 안 된…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
324 323 3498. Reverse Degree of a String
각 문자의 뒤집은 알파벳 순번과 1부터 센 위치를 곱해서 전부 더하는 문제. 그냥 한 번 죽 돌면서 곱해서 더해주면 된다. 파이썬은 char 타입이 없어서 C++처럼 c - 'a'를 못 쓴다. ord(c) - ord('a')로 코드포인트를 빼줘야 한다. 뒤집은 알파벳 순번은 거기서 26 - (ord(c) - ord('a')). 위치가 1부터라 i+1이고, …
322 1401. Circle and Rectangle Overlapping
원과 축에 나란한 직사각형이 겹치는지 판정하는 문제. 일단 좌표 범위가 작아서 테두리의 정수 점을 전부 돌려봤다. 입력이 전부 정수라 가장 가까운 점도 정수라서 이걸로도 통과는 된다. 근데 그럴 필요가 없다. 원 중심에서 가장 가까운 직사각형 위의 점 하나만 보면 되고, 그 점은 좌표를 구간에 자른 (min(max(x1, xCenter), x2), min(…
321 1520. Maximum Number of Non-Overlapping Substrings
어떤 문자를 담으면 그 문자가 나오는 모든 위치를 담아야 한다는 조건 아래, 겹치지 않는 부분 문자열을 최대 개수로 고르는 문제. 일단 알파벳별로 first, last 인덱스를 뽑아둔다. 시작점 후보는 각 알파벳의 first, 26개뿐이다. 거기서 오른쪽으로 훑으면서 보이는 문자의 last로 end를 늘려주면 된다. 대신 중간에 first[cc] < sta…
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개를 고르는 문제인데 이번엔 최대 개수가 아니라 경우의 수다. 한 점에서 할 수 있는 건 이어붙이기, 끊고 넘어가기, 새로…
318 2472. Maximum Number of Non-overlapping Palindrome Substrings
문자열 s에서 길이가 k 이상인 팰린드롬 부분 문자열을 서로 겹치지 않게 최대 몇 개 고를 수 있는지 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 팰린드롬 판별도 isPalindrome(l, r)로 DP를 두면 전체가 O(n^2)이 된다. 처음엔 너무 편하게 둘 다 @cache를 붙였다가 메모리 초과가 났다... isPalindro…
317 836. Rectangle Overlap
축에 평행한 직사각형 두 개가 주어질 때, 교집합의 넓이가 양수인지 판단하는 문제. 변이나 꼭짓점만 닿는 것은 겹치지 않는 것으로 본다. easy지만 생각보다 easy하지 않은 문제. 처음엔 한쪽의 끝점이나 꼭짓점이 상대 직사각형 안에 들어가는지로 판단하려 했다. 그런데 한쪽이 다른 쪽을 품는 경우나 십자 모양으로 겹치는 경우를 놓치고, 경계 처리도 계속 …
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을 실제로 옮겨 그려서 셌는데 시간 초과가 났다. 이동할 때마다 보드…