[JAVA] 백준 13711번 : LCS 4

---

 

• 코드

실패 코드 : 기존 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);
	}
}