[백준(Baekjoon)][자바(java)] 12015 : 가장 긴 증가하는 부분 수열 2 / 이분 탐색

 

www.acmicpc.net/problem/12015

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

 

1.  브루트 포스  --> 시간 초과

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), a[] = new int[n], i, j;
		for (i = 0; i < n; ++i)
			a[i] = sc.nextInt();
		sc.close();
		
		int len = 0, cnt;
		for (i = 0; i < n; ++i) {
			cnt = 1;
			for (j = i + 1; j < n; ++j) {
				if( a[i] < a[j] ) {
					cnt++;
					a[i] = a[j];
				}
			}
			if (len < cnt) len = cnt;
		}
		System.out.println(len);
	}
}

 

 

2.  동적 계획법  --> 시간 초과  ( '11053 : 가장 긴 증가하는 부분 수열' 문제에 비해 입력 값 범위가 커짐 )

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), i, j;
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();

		int[] a = new int[n], dp = new int[n];
		int len = 0;

		dp[0] = 1;
		for (i = 0; i < n; ++i) {
			a[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
			for (j = 0; j < i; ++j)
				if (a[j] < a[i] && dp[j] >= dp[i])
					dp[i]++;
			if (len < dp[i]) 
				len = dp[i];
		}

		System.out.println(len);
	}
}

 

 

3.  이분 탐색

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), i;
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();

		int value, left, right, mid, end;

		List<Integer> list = new ArrayList<>(); // 증가하는 부분 수열을 리스트에 넣음
		list.add(0); // 수열의 최솟값이 1이므로 비교를 위해 0을 미리 넣어줌

		for (i = 0; i < n; i++) {
			value = Integer.parseInt(st.nextToken()); 
			end = list.size() - 1;
			if (value > list.get(end))
				// 수열의 값이 리스트의 맨 끝 값보다 크면 리스트에 넣음
				list.add(value); 
			else {
				// 〃 작으면 리스트 안에서 이분탐색을 하여 알맞은 자리에 값을 대치
				left = 0;
				right = end;
				while (left < right) {
					mid = (left + right) / 2; // ( >> 1 )
					if (value <= list.get(mid))
						right = mid;
					else
						left = mid + 1;
				}
				list.set(right, value);
			}
		}
		System.out.println(list.size() - 1);
	}
}

코드 참고 : https://dragon-h.tistory.com/2