백준 11053 JAVA : 가장 긴 증가하는 부분 수열(LIS)

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

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

 

---

최장 증가 부분 수열(LIS : Longest Increasing Subsequence) 과 같은 것이다.

 

풀이방법1 - dp

1. dp[]배열을 생성한다.(i번째 원소를 마지막원소로 가지는 LIS 길이)
2. 이전 nums[]값들을 순회하면서 지금 위치의 nums값이 더 크면  이전dp[]값+1 과 현재 dp[]값 중 큰 값을 넣어줌
3. 결과값을 갱신해줌

소스코드

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

public class Main {
	static int N;
	static int[] nums;
	static int[] dp;
	static int result;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		dp = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		result = 1; //해주는 이유 : 입력 1,1 일 때 0 출력된다.
		for (int i = 0; i < N; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) { //이전 값들을 순회
				if(nums[i] > nums[j]) { //지금 위치의 번호가 더 크면
					dp[i] = Math.max(dp[i], dp[j]+1); //dp 현위치 값을 바꿔줌
					result = Math.max(result, dp[i]); //결과값 갱신
				}
			}
		}
		System.out.println(result);
	}

}

 

풀이방법2 - 이분탐색

이분탐색으로 풀면, 이 문제도 통과 가능하다(dp로 풀면 O(N^2)의 시간복잡도가 들기 때문, 이분탐색: O(NlogN)) 

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

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

 

이분탐색 풀이를 하기 전에, 이분탐색 내장함수를 알아보자

Arrays.binarySearch 함수는 기본적으로 정렬되어있다는 전제로 사용한다.

 

Arrays.binarySearch(배열명, 타겟)

int[] nums = {20,10,30,10};

System.out.println("20의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 20));
System.out.println("첫번째 10의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 10));
System.out.println("25의 위치 값 반환(없는 수는 음수) ==> "+Arrays.binarySearch(nums, 25));

 

1. 값이 있다면 그 값의 위치 값 반환
2. 값이 있다면 그 값의 제일 앞 위치 값 반환
3. 값이 없다면 그 값이 들어가야 할 자리의 음수 값 -1 반환

 

Arrays.binarySearch(배열명, 시작인덱스, 끝인덱스+1,타겟)

int[] nums = {10,20,30,40,0,0,0};
		
/*-5가 나와야하는데 뒷 배열이 빈 배열이라 뒤에까지 탐색해서 -8 반환된다.*/
System.out.println("1. 25의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 80));
		
System.out.println("2. 인덱스 0~2, 30의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 0, 3, 30));
System.out.println("3. 인덱스 0~1, 30의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 0, 2, 30));
System.out.println("4. 인덱스 0~6, 25의 위치 값 반환 ==> "+Arrays.binarySearch(nums, 0, nums.length, 25));

 

1. 배열 안에 있는 원소보다 큰 값 && 없는 값을 넣으려고 할 때 파라미터가 2개인 내장함수를 쓴다면 끝까지 탐색하므로 -(배열크기+1) 를 반환, 이러한 문제를 방지하기 위해 파라미터가 4개인 내장함수를 사용!!
2. 범위 안에 값이 있다면 그 값의 위치 값 반환
3. 범위 안에 값이 없다면 그 값이 들어가야 할 자리의 음수 값 -1 반환
4. 범위 안에 값이 없다면 그 값이  들어가야 할 자리의 음수 값 -1 반환

 

 

풀이 방법

1. binary 배열을 하나 만들고 수열을 저장한다.
2. binary 배열 마지막 값 보다 큰 수가 들어오면 그 다음 인덱스에 숫자를저장한다.
3. binary 배열 마지막 값보다 작거나 같은 수가 들어오면 binarySearch 함수를 통해 인덱스를 받는다.
4. 인덱스가 양수이면 그 자리에 수를 넣고 인덱스가 음수라면 |index+1| 자리에 수를 넣는다.

nums[] = {10,20,10,30,20,50} 일 때 binary[] 배열 과정

1. 초기값 binary[0] 에 nums[0] 값을 넣어줌
2. 20이 들어 올 때, binary 배열 마지막 값인 10 보다 큰 수 이므로 다음 인덱스에 20을 저장
3. 10이 들어올 때, binary 배열 마지막 값인 20 보다 작은 수 이므로 binarySearch 로 인덱스를 받아(0) 그곳에 10을 저장
4. 30이 들어올 때, binary 배열 마지막 값인 20 보다 큰 수 이므로 다음 인덱스에 30을 저장
5. 20이 들어올 때, binary 배열 마지막 값인 30 보다 작은 수 이므로 binarySearch 로 인덱스를 받아(1) 그곳에 20을 저장
6. 50이 들어올 때, binary 배열 마지막 값인 30 보다 큰 수 이므로 다음 인덱스에 50을 저장

 

nums[] = {4,8,9,1,2,6,7} 일 때 binary[] 배열 과정

1. 초기값 binary[0] 에 nums[0] 값을 넣어줌
2. 8이 들어올 때, binary 배열 마지막 값인 4 보다 큰 수 이므로 다음 인덱스에 8을 저장
3. 9가 들어올 때, binary 배열 마지막 값인 8 보다 큰 수 이므로 다음 인덱스에 9을 저장
4. 1이 들어올 때, binary 배열 마지막 값인 9 보다 작은 수 이므로 binarySearch 로 인덱스를 받음(-1) => 인덱스가 음수이므로 |index+1|  = 0자리에 1을 저장
5. 2가 들어올 때, binary 배열 마지막 값인 9 보다 작은 수 이므로 binarySearch 로 인덱스를 받음(-2) => 인덱스가 음수이므로 |index+1|  = 1자리에 2를 저장
6. 6이 들어올 때, binary 배열 마지막 값인 9 보다 작은 수 이므로 binarySearch 로 인덱스를 받음(-3) => 인덱스가 음수이므로 |index+1|  = 2자리에 6를 저장
7. 7이 들어올 때, binary 배열 마지막 값인 6 보다 큰 수 이므로 다음 인덱스에 7을 저장

 

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] nums;
	static int[] binary;
	static int result;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		binary = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int index = 0; //이분탐색 인덱스(마지막)
		
		binary[0] = nums[0]; //초기 값을 넣어준다.
		
		for (int i = 1; i < N; i++) {
			if(nums[i] > binary[index]) { //숫자가 binary배열 마지막값보다 클 때
				binary[++index] = nums[i];
			}else { //숫자가 binary배열 마지막 값보다 작거나 같을 때
				int temp = Arrays.binarySearch(binary, 0, index, nums[i]); //위치반환
				if(temp < 0) { //음수라면 +1한 값의 절댓값
					temp = Math.abs(temp+1);
				}
				binary[temp] = nums[i];
			}
		}
		
		//binary 크기 계산
		for (int i = N-1; i >= 0; i--) {
			if(binary[i] != 0) {
				System.out.println(i+1);
				break;
			}
		}
	}

}

 

결과(11053 : 위 - dp풀이, 밑 - 이분탐색)

결과(12015 : 이분탐색,dp-> 시간초과)