[JAVA | 백준] 12015: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

제출 답안

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        int[] answer = new int[n];
        
        answer[0]=nums[0];        // 첫번째 원소 추가
        int answerLength= 1;

        for(int i=0;i<n;i++){

            if (answer[answerLength-1]<nums[i]){  
                // 정답배열의 마지막 원소 < 새로 들어올 원소 
                answer[answerLength]=nums[i];
                answerLength++;
            }else{
                // 정답배열의 마지막 원소 >= 새로 들어올 원소 
                // 이진 탐색으로 삽입될 위치를 찾음
                int left = 0, right = answerLength-1, idx = 0;
                while (left <= right) {
                    int mid = (left+right)/2;
                    if (answer[mid] >= nums[i]) {
                        idx = mid;
                        right = mid-1;
                    } else {
                        left = mid+1;
                    }
                }
                
                // 정답배열의 첫번째 원소보다 새로 들어올 원소가 작다면
                if (nums[i] <= answer[0]) {
                    answer[0] = nums[i];
                } else {  // 새로 들어올 원소로 변경
                    answer[idx] = nums[i];
                }
            }
        }
        System.out.println(answerLength);
        br.close();
    }
}

 

개선 답안

• ArrayList + BufferedWriter

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] arr;
	static ArrayList<Integer> dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;

		int ans = 0;
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		dp = new ArrayList<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; ++i) {
			if (dp.size() == 0 || dp.get(dp.size() - 1) < arr[i]) {
				dp.add(arr[i]);
			} else {
				int left = 0;
				int right = dp.size() - 1;
				while (left < right) {
					int mid = (left + right) >> 1;
					if(dp.get(mid) >= arr[i]) {
						right = mid;
					} else {
						left = mid + 1;
					}
				}
				dp.set(right, arr[i]);
			}
		}

		bw.write(dp.size() + "\n");
		bw.close();
	}
}

 

 

참고 자료

https://gre-eny.tistory.com/23

[java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2

https://st-lab.tistory.com/285

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]

https://j3sung.tistory.com/m/945

[Java] 백준 12015번 가장 긴 증가하는 부분 수열 2