PS 일지

문제길이 $n$인 정수 배열 $\texttt{nums}$가 주어지며, 배열의 각 원소는 $1$ 이상 $n$ 이하이다. $(n \le 10^5)$$1$ 이상 $n$ 이하의 정수 중, $\texttt{nums}$에 포함되어 있지 않은 수들을 리스트에 담아 반환해라. 추가 조건1. 리턴할 리스트를 제외하고 추가 공간 사용 x2. 시간복잡도 $O(n)$으로 해결 시도추가 조건대로 풀어보기 위해 많은 생각을 해봤다. 1. 해시셋을 써봐야겠다 -> 추가 공간 사용함2. 1부터 하나씩 배열에 있는지 볼까? -> $O(n^2)$임3. 정렬하면 공간을 안 쓰고 할 수 있을 것 같다. -> $O(n\log{n})$임4. 각 비트가 몇 번 나왔는지 볼까? -> $O(n\log{n})$이고 공간도 더 씀 한 시간 정도 고민해..

문제$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 = (..

문제https://www.acmicpc.net/problem/5214$N$개의 역과 $M$개의 하이퍼튜브가 존재하며, 하이퍼튜브 하나는 역 $K$개를 서로 연결한다.$1$번 역에서 $N$번 역으로 가는데 방문하는 최소 역의 수를 구해보자. 풀이하나의 하이퍼튜브가 연결하는 $K$개의 역을 서로 모두 이어주게 된다면, 간선이 $\dfrac{K(K-1)}{2}$개 생기게 된다.아래는 2, 4, 5, 7, 8, 9번 역을 연결하는 하이퍼튜브를 그래프에 추가시킨 그림이다.이 방식대로 그래프를 구성한다면 전체 간선은 $O(MK^2)$만큼 생기게 되고, 이는 메모리나 시간의 제약으로 인해 불가능한 풀이가 된다.하이퍼튜브 하나를 그래프의 새로운 가상의 정점으로 본다면 어떨까?하나의 하이퍼튜브로 인해 추가되는 간선은 $..

문제https://www.acmicpc.net/problem/9376두 명의 죄수가 $H \times W$ 크기의 감옥에 갇혀 있다.감옥을 구성하는 격자 칸은 빈 칸('.'), 벽('*'), 문('#'), 죄수('$')로 이루어져 있다.두 죄수가 모두 감옥의 바깥으로 탈출하기 위해 열어야 하는 문의 최소 개수를 구하는 문제이다.풀이문의 개수가 충분히 적다면 문의 열림/닫힘 상태를 관리하는 비트마스킹 + BFS로 해결할 수 있으나, 이 문제에서는 먹히지 않는다. 답이 나올 수 있는 경우를 두 가지로 나눠보았다.1. 두 명의 죄수가 만나지 않고 각각 탈출하는 경우각 죄수를 시작점으로 두고 다익스트라 혹은 0-1 BFS로 탈출하는 최단 경로를 구한다.2. 두 명의 죄수가 만나서 같이 탈출하는 경우첫 번째 죄수..

문제https://www.acmicpc.net/problem/9328여러 요소들로 이루어진 2차원 격자가 주어진다. 존재하는 요소는 벽$($*$)$, 빈 공간$($.$)$, 문서$($$\$)$, 문$($알파벳 대문자$)$와 각 알파벳에 대응하는 열쇠$($알파벳 소문자$)$들이 있다.상하좌우로 인접한 칸으로만 이동할 수 있고, 경계에 존재하는 빈 공간으로 격자 안과 밖을 오갈 수 있을 때, 얻을 수 있는 문서 개수의 최댓값을 구하는 문제이다. 풀이갈 수 있는 곳들에서 열쇠를 새로 먹어주고, 먹은 열쇠로 열 수 있는 문을 찾아 갈 수 있는 곳을 확장시켜주는 작업을 계속 반복한다.더이상 변화가 생기지 않을 때까지 이를 반복하고, 그 때까지 모은 문서의 수를 출력해주면 된다. import java.util.*;..

문제https://www.acmicpc.net/problem/28060, 1로만 이루어진 길이 $N$인 1-based index 수열 $S$에, $1 \le i \le N$을 골라서 아래 두 가지 연산을 할 수 있다.1. $S[i] = S[i] \oplus 1$2. $S[1] = S[1] \oplus 1, \cdots, S[i] = S[i] \oplus 1$$ \oplus $는 exclusive or를 의미한다.모든 원소를 $0$으로 만드는 데 필요한 최소 연산 횟수를 구하는 문제이다.풀이$1$인 원소를 $0$으로 만드는 방법에는 아래 것들이 존재한다.1. 모든 원소 $1$에 대해, 1번 연산 수행하기2. 특정 구간 $[l,r]$의 원소가 모두 $1$일 때, 2번 연산을 각각 $i = l-1, i=r$로..

문제https://www.acmicpc.net/problem/147160과 1로만 이루어진 2차원 격자가 주어진다.1이 격자 상에서 인접한 8방향으로 연결되어있다면 연결 요소 전체를 한 글자로 볼 때,총 연결 요소의 수를 구하는 문제이다. 풀이격자를 순회하며 1을 만날 때마다 BFS로 연결 요소를 모두 방문처리한 후 글자 수를 올려주었다. import java.util.*;import java.io.*;class Node{ int x; int y; Node(int x, int y){ this.x = x; this.y = y; }}public class Main { static StringTokenizer st; static int nextInt()..