- 코드
정답 코드 : 가장 긴 증가하는 부분 수열은 dp로 풀었었는데, dp로 풀게되면 문제가 N의 수가 높아질 경우 시간 복잡도가 O(N^2)이기 때문에 너무 오래걸린다. 해결책은 LIS 알고리즘이다. LIS 알고리즘은 시간 복잡도 O(NlogN)이다.
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
static int N, answer;
static int[] inputArray, LIS;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
inputArray = new int[N];
LIS = new int[N];
answer = 0;
for (int i = 0; i < N; i++) {
inputArray[i] = in.nextInt();
}
LIS[0] = inputArray[0];
int j = 0;
for (int i = 1; i < N; i++) {
if (LIS[j] < inputArray[i]) {
LIS[++j] = inputArray[i];
} else {
int temp = binarySearch(0, j, inputArray[i]);
LIS[temp] = Math.min(LIS[temp], inputArray[i]);
}
}
answer = j + 1;
}
static int binarySearch(int startIndex, int endIndex, int key) {
while (startIndex <= endIndex) {
int mid = (startIndex + endIndex) / 2;
if (LIS[mid] < key) {
startIndex = mid + 1;
} else {
endIndex = mid - 1;
}
}
return startIndex;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- LIS 알고리즘
LIS 알고리즘은 주어진 수열 내에서 가장 긴 부분 수열을 찾아내는 알고리즘이다.
최적화의 핵심은 Binary Search이다. 위의 dp처럼 O(N)의 방법으로 수열을 처음부터 확인할건데 이번에는 이분탐색을 이용하여 LIS를 유지하기 위한 최적의 위치에다가 수를 삽입하는 방식입니다.
'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 2866번 : 문자열 잘라내기 (0) | 2021.09.08 |
|---|---|
| [BOJ/JAVA] 백준 14725번 : 개미굴 (0) | 2021.09.07 |
| [BOJ/JAVA] 백준 2617번 : 구슬 찾기 (0) | 2021.08.27 |
| [BOJ/JAVA] 백준 10800번 : 컬러볼 (0) | 2021.08.26 |
| [BOJ/JAVA] 백준 10653번 : 마라톤 2 (0) | 2021.08.17 |
