- 코드
실패 코드 : 기존 LCS 방식으로 해보았다. 결과는 메모리 초과, int[]를 stringbuilder로도 해봤지만 메모리 초과
메모리 초과의 이유는 (10만x10만xsizeof(int))이기 때문이였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long input = Long.parseLong(br.readLine());
int[] firstArray = new int[(int) input];
int[] secondArray = new int[(int) input];
StringTokenizer string = new StringTokenizer(br.readLine());
for(long i=0;i<input;i++) {
firstArray[(int) i] = Integer.parseInt(string.nextToken());
}
string = new StringTokenizer(br.readLine());
for(long i=0;i<input;i++) {
secondArray[(int) i] = Integer.parseInt(string.nextToken());
}
int[][] dp = new int[(int) (input + 1)][(int) (input + 1)];
for (int i = 1; i <= firstArray.length; i++) {
for (int j = 1; j <= secondArray.length; j++) {
if (firstArray[i-1] == secondArray[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
System.out.println(dp[firstArray.length][secondArray.length]);
}
}
성공 코드 : 첫번째 배열을 LIS배열에 순서대로 넣고, 두번째 배열을 LIS 알고리즘에 따라서 풀었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int input = Integer.parseInt(br.readLine());
int[] LIS = new int[input + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= input; i++)
LIS[Integer.parseInt(st.nextToken())] = i;
int[] arrays = new int[input];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < input; i++)
arrays[i] = LIS[Integer.parseInt(st.nextToken())];
int j = 0;
LIS[j++] = arrays[0];
for (int i = 1; i < input; i++) {
int index = Arrays.binarySearch(LIS, 0, j, arrays[i]);
if (index == -(j + 1))
LIS[j++] = arrays[i];
else
LIS[-(index + 1)] = arrays[i];
}
System.out.print(j);
}
}
'algorithm' 카테고리의 다른 글
| [JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3 (0) | 2020.08.28 |
|---|---|
| [JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열 (0) | 2020.08.28 |
| [JAVA] 백준 1958번 : LCS 3 (0) | 2020.08.27 |
| [JAVA] 백준 1027번 : 고층 건물 (0) | 2020.08.27 |
| [JAVA] 백준 1644번 : 소수의 연속합 (0) | 2020.08.26 |
