PS 일지

문제$0$과 $1$로만 이루어진 문자열 $s$가 주어진다.문자열의 인덱스 $i$에서 $[i+\texttt{minJump}, i+\texttt{maxJump}]$ 범위 내의 값이 $1$인 인덱스로 점프할 수 있다.단, 인덱스가 문자열의 경계를 넘어가서는 안 된다. 인덱스 $0$에서 $s.\texttt{length}-1$로 점프할 수 있는지 알아보자.풀이거꾸로 생각해보자. 인덱스 $i$로 도달할 수 있을 조건이 무엇일까?$[i-\texttt{maxJump}, i-\texttt{minJump}]$ 범위에서 도달 가능한 인덱스 $j$가 적어도 하나 있어야 한다. $\texttt{reach}[i]$를 인덱스 $i$로 도달 가능하면 true, 아니면 false라고 정의하자. 인덱스 $i$를 반복문으로 순회한다면, ..

문제정수 배열 $arr$과 $1$ 이상의 정수 $d$가 주어진다.인덱스 $i$에서 아래 조건을 만족시키면 인덱스 $j$로 점프할 수 있다.$arr[j] $\max(i-d, 0) \le j \le \min(i+d, \texttt{arr.length})$$\min(i, j) 풀이인덱스 $i$로 점프할 수 있는 조건을 해석하면 다음과 같다.인덱스 $i$의 양쪽으로, 거리 $d$ 이하의 $arr[i]$보다 큰 가장 가까운 원소거리 조건만 빠지면, 스택을 응용하는 문제로 변한다.즉, 점프를 통해 인덱스 $i$를 방문할 수 있는 곳은 좌우 각각 한 군데로 정해진다.가장 가까운 원소가 아니더라도 점프를 할 수 있지만, 그 경우에는 항상 최적이 아니다.간단한 반례를 들면, $i 거리 조건을 모두 만족한다면, $k$에서..

문제두 정수 배열 $arr1, arr2$가 있다.$1 \le i \le |arr1|, 1 \le j \le |arr2|$인 $i, j$에 대해,$arr1_i$와 $arr2_j$의 Longest Common Prefix 중 가장 큰 값을 구해보자.풀이두 배열의 크기 제한이 모두 $50,000$이기 때문에, 완전 탐색을 하면 시간 초과가 날 것 같다.배열의 원소를 정수가 아니라 문자열로 본다면, 문자열 집합에서 특정 문자열을 검색하는 문제로 바꿀 수 있다.문자열 집합에서 검색을 지원하는 자료 구조인 트라이를 사용해보자.$arr1$의 모든 원소를 트라이에 삽입해놓고, $arr2$의 원소를 하나씩 트라이에서 검색한다.검색할 때는, 검색 문자열과 일치하는 최대 깊이까지 내려가면 된다.코드class TrieNode..

문제정렬된 두 정수 배열 $nums1$, $nums2$ 가 주어진다.두 배열의 중앙값을 $\log$ 시간복잡도로 구해보자.풀이문제를 살짝 변형해서, 두 배열의 $k$번째 원소를 구해보자.$k$번째 원소를 어떻게 구할까?아직은 모르지만, $k$번째 원소의 값을 $v$라고 하자.어떤 값 $x$가 $v$보다 작다면 두 배열에서 인덱스가 $k$ 미만이다.따라서 $x$를 매개 변수로 두고 이분 탐색을 진행하며 가능한 $x$의 범위를 빠르게 좁혀나갈 수 있다.두 배열에서 어떤 값 $x$의 인덱스는 이분 탐색으로 빠르게 구할 수 있다.코드class Solution { public int upperBound(int[] arr, int x) { int s = 0, e = arr.length, m = (..