R+7

문제단어 조각을 무한히 사용해 문자열 t를 만드는 최소 조각 수를 구한다. 만들 수 없으면 -1을 반환한다. 조각은 최대 100개, 길이는 1~5이며 t의 길이는 최대 20,000이다. 예를 들어 banana는 ba, na, na로 만들면 3개가 필요하다.회고문자열 DP와 집합 문제. 핵심은 앞에서 i글자를 만드는 최소 조각 수를 저장하고, 조각 길이가 최대 5라는 제한으로 안쪽 반복을 줄이는 것. 처음에는 조각을 붙이는 모든 경로를 백트래킹했다. 하지만 같은 접두사를 만드는 경로를 반복 탐색한다. 같은 위치까지 2개로 도달했다면 3개로 도달한 경로는 이후에도 이득이 없으므로 최소 개수만 남기면 된다.def solution(strs, t): answer = 1e9 strs.sort(key=la..

문제?가 접두사 또는 접미사에 연속으로 붙은 검색어마다 일치하는 단어 수를 구한다. ? 하나는 문자 하나와 대응하므로 단어 길이도 같아야 한다. 단어와 검색어는 각각 최대 100,000개, 전체 문자열 길이의 합은 각각 최대 1,000,000이다. 예를 들어 fro??는 frodo, front, frost와 일치한다. 모든 단어를 검색어마다 비교하면 효율성을 만족하기 어렵다.회고트라이 문제. 핵심은 정방향과 역방향 트라이를 만들고, 각 노드에 단어 길이별 개수를 저장하는 것.fro??는 정방향 트라이에서 fro까지만 이동한다.????o는 뒤집으면 o????가 되므로 역방향 트라이에서 o까지만 이동한다.도착한 노드에서 검색어 길이에 해당하는 개수를 읽는다. 같은 접두사여도 길이가 다르면 제외된다.?????..

문제서로 맞닿은 두 연속 구간을 골라 합을 같게 만들고, 한쪽 합의 최댓값을 구한다. 바구니는 최대 2,000개이며 원소는 모두 양수다. [1, 1, 2, 3]의 답은 3이고, 같은 합을 만들 수 없는 [1, 2, 4, 5]의 답은 0이다.회고누적합과 투 포인터 문제다. 핵심은 두 구간의 경계 m을 고정하고 양쪽으로 확장하는 것. m은 중앙값이 아니라 나눌 위치이며, 가능한 경계를 전부 순회한다.누적합으로 왼쪽 합 P[m] - P[l], 오른쪽 합 P[r] - P[m]을 O(1)에 계산한다.왼쪽 합이 작으면 l을 줄이고, 오른쪽 합이 작으면 r을 늘린다. 같으면 답을 갱신하고 양쪽을 확장한다.모든 원소가 양수라 구간을 넓히면 합이 커진다. 그래서 작은 합 쪽을 늘리면 된다.경계 하나에서 두 포인터는 되돌..

문제두 사람이 중심에서 2m, 3m, 4m 떨어진 좌석 중 하나씩 골라 앉았을 때, 무게 × 거리가 같아지는 사람 쌍의 수를 구한다. 사람은 최대 100,000명이며, 같은 무게의 서로 다른 사람도 한 쌍으로 센다.회고해시 카운팅 문제다. 핵심은 사람을 일일이 비교하지 않고, 균형이 가능한 무게 비율의 인원수를 더하는 것.무게를 정렬해 처리하면 현재 무게 w의 상대는 w, 2w, 3w/2, 4w/3만 확인하면 된다. 분수는 정수로 나누어떨어질 때만 조회한다.현재 사람의 빈도를 먼저 1 줄이고 남은 인원만 센다. 자신과 짝짓거나 같은 쌍을 두 번 세는 일을 막는다.원래 코드의 w/2, 2w/3은 정렬 순서상 이미 처리한 무게라 빈도가 0이다. 정리한 코드에서는 생략한다.정렬 O(N log N), 사람마다 ..

문제연속 부분 수열에 [1, -1, 1, …] 또는 [-1, 1, -1, …]을 곱했을 때 합의 최댓값을 구한다. 길이는 최대 500,000이다. 예제 [2, 3, -6, 1, 3, -1, 2, 4]의 답은 10이다.회고DP, 카데인 알고리즘 문제다. 핵심은 한 가지 펄스를 전체 수열에 적용한 뒤, 최대 연속 합과 최소 연속 합을 함께 구하는 것.짝수 인덱스의 부호를 뒤집는다. 반대 펄스의 구간 합은 현재 구간 합에 -1을 곱한 값이다.max_dp[i]는 i에서 끝나는 최대 연속 합이다. 이전 구간에 현재 값을 붙일지, 현재 값부터 새로 시작할지 고른다.min_dp[i]도 같은 방식으로 최솟값을 고른다. 답은 max(max(max_dp), -min(min_dp))다.첫 칸은 부호를 바꾼 sequence[..

문제기둥과 보의 설치, 삭제 명령을 처리하되 모든 구조물이 지지 조건을 만족해야 한다. 조건을 어기는 명령은 무시하고, 마지막 구조물을 x, y, 종류 순으로 정렬해 반환한다.회고구현, 시뮬레이션 문제다. 핵심은 일단 명령을 적용하고, 전체 구조물을 검사한 뒤 잘못됐으면 되돌리는 것. 설치와 삭제의 모든 주변 상황을 따로 나누려다 복잡해졌던 부분을 공통 검증 함수로 정리했다.기둥은 바닥 위, 다른 기둥 위, 보의 한쪽 끝 위 중 하나면 유효하다.보는 한쪽 끝이 기둥 위에 있거나, 양쪽 끝이 다른 보와 연결되어 있으면 유효하다.설치는 추가 후 검사, 삭제는 제거 후 검사한다. 하나라도 유효하지 않으면 방금 한 작업을 원복한다.구조물은 (x, y, a) 튜플로 set에 저장한다. 이웃 구조물의 존재를 평균 ..

문제규칙대로 채운 n × n 배열을 일렬로 펼쳤을 때 left부터 right까지의 값만 반환한다. n은 최대 10⁷이지만 반환 구간은 최대 100,000개다. 배열의 각 칸 값은 0부터 센 행과 열 중 큰 값에 1을 더한 값이다.문제와 배열 생성 그림 보기회고인덱스 변환 문제다. 핵심은 배열을 만들지 않고 필요한 위치의 값만 계산하는 것.펼친 배열의 인덱스 i를 행 i // n, 열 i % n으로 바꾼다.그 위치의 값은 max(i // n, i % n) + 1이다. 코드에서는 행과 열에 각각 1을 더한 뒤 max를 구한다.left부터 right까지, 양 끝을 포함해 순회한다.전체 배열은 최대 10¹⁴칸이므로 생성할 수 없다. 필요한 K = right - left + 1개만 계산하면 시간 O(K), 반환 ..

문제N × N 시계 격자에서 하나를 돌리면 자신과 상하좌우 시계가 함께 90도 회전한다. 모든 시계를 12시로 맞추는 최소 회전 수를 구한다. N은 최대 8이며, 시계 값은 0부터 3이다.회고첫 행 완전탐색과 시뮬레이션 문제다. 핵심은 첫 행의 회전 수만 고르면 나머지 행은 윗행을 0으로 맞추도록 강제된다는 것. 주변 상태만 보고 돌리는 그리디로는 전체 최솟값을 보장할 수 없다.첫 행의 각 칸을 0~3번 돌리는 모든 조합을 탐색한다. 경우의 수는 4ᴺ이다.둘째 행부터 현재 칸 위의 값이 k라면 (4 - k) % 4번 돌린다. 이후 더 아래 행은 그 윗칸에 닿지 못하므로 이 선택은 필수다.마지막 행까지 처리한 뒤 마지막 행이 모두 0이면 회전 수로 답을 갱신한다. 각 첫 행 조합은 원본 격자를 복사해 독립..

문제바위 n개를 제거해 출발점부터 도착점까지의 인접 간격 중 최솟값을 최대화한다. 바위는 최대 50,000개, 도착 거리 D는 최대 10억이다.회고이분 탐색, 매개변수 탐색 문제다. 핵심은 제거할 바위 조합 대신, 최소 간격 x를 유지할 수 있는지 판단하는 것.바위를 정렬하고 마지막으로 남긴 위치 curr부터 간격을 확인한다. 간격이 mid보다 작으면 현재 바위를 제거하고 cnt를 늘린다.도착점과 마지막으로 남긴 바위 사이의 간격도 검사한다.cnt ≤ n이면 mid를 만들 수 있다. answer를 갱신하고 low = mid + 1로 더 큰 간격을 탐색한다. cnt > n이면 high = mid - 1로 줄인다.간격 기준을 키울수록 필요한 제거 수가 줄어들지는 않는다. 이 단조성 때문에 이분 탐색이 가능하..