백준 12015 java - 가장 긴 증가하는 부분 수열 2(이진 탐색/2가지 풀이)

문제, 입출력, 테스트케이스

어제 오늘은 이진탐색 부수기를 하고 있다.

드디어 백준 단계별로 풀기에서 이진탐색을 밀었다!

25단계까지 총 5문제 남았다!

이진 탐색에 대해서 심리적 거부감이 있던 터라 극복하면 보이지 않는 벽을 부순다는 일념으로 열심히 도전했다.

 

이진 탐색은 결국 매개변수 탐색과 연결된다는 점이 핵심인 것 같다.

 

풀이는 List 활용 방식과 Array(배열) 탐색 방식이며 Array방식이 시간이 더 짧다. ( 756ms[List] > 592ms[Array])

<문제 접근/풀이 방식>
1. 이진탐색(매개변수 탐색)을 사용하기 위해서는 다음 두 가지 조건이 필요하다.
1.1 순차대로 탐색이 가능해야한다.
1.2 특정 단절점이 있어야 한다.
2. 거진 반나절을 꼬박 생각해도 특정 위 두 가지 조건에 맞추는 방법을 생각지 못해서 구글링을 했더니 list 풀이 방식이 나왔다.
3. List는 남의 접근법이므로 배열로 풀어야 내가 실전에서 쓸 수 있을 것 같아서 배열로 풀어보았다.
4. 풀이는 다음과 같다.(배열 풀이로 설명 -> 본인이 직접 푼 풀이에 해당하므로)
5 10 15 1 2 3이라는 값이 들어 왔을 때, 배열은 +1만큼 패딩해서 [0, 0, 0, 0, 0, 0, 0](7개의 배열 선언), lastIndex = 1인 상황

5 입력  
lastIndex = 1이므로 배열의 lastIndex-1 번째 값과 비교해보니 5가 더 커서 lastIndex에 값을 넣고 index++;
배열 값 : [0, 5, 0, 0, 0, 0, 0] / lastIndex = 2

10 입력
lastIndex = 2임로 배열의 lastIndex-1 번째 값과 비교해보니 10이 더 커서 위와 동일하게 적용
배열 값 : [0, 5, 10, 0, 0, 0, 0] / lastIndex = 3

15 입력
위와 동일
배열 값 : [0, 5, 10, 15, 0, 0, 0] / lastIndex = 4

1 입력
lastIndex-1 번째 값과 비교 해보니 1이 더 작아서 이진탐색을 통해 1이 들어갈 인덱스 탐색
index 1번째에 들어갈 수 있음
배열 값 : [0, 1, 10, 15, 0, 0, 0] / lastIndex = 4

2 입력
위와 동일한 과정 거쳐서
배열 값 : [0, 1, 2, 15, 0, 0, 0] / lastIndex = 4

3 입력
위와 동일한 과정 거쳐서
배열 값 : [0, 1, 2, 3, 0, 0, 0] / lastIndex = 4

답은 lastIndex -1을 출력하면 된다.
 
소스코드를 보면 더 이해가 쉬울 것이다. 우리는 개발자니까!

 

<List를 활용한 소스코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static List<Integer> answer;
	public static void main(String[] args) throws IOException {
		// 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)
		// Ai (1 ≤ Ai ≤ 1,000,000)
		// NlogN의 시간 복잡도를 가져야 함
		
		// 10 20 10 30 20 50 
		// 1  2  1  3  2  4
		// 이진탐색을 활용해서 풀어보자
		// 단절이 발생하는가
		// 1. 특정 수를 선택
		// 2. 그 수 보다 낮으면서 누적 횟수가 가장 많은 경우 + 1
		// 3. 단절성이 있어야 함, 순서대로 탐색을 해도 무방해야 함.
		// 10 20 10 15 20 30 30 50
		// 1  2  1  2  3  4  4  5
		// 1 : 10, 10
		// 2 : 15, 20
		// 3 : 20
		// 4 : 30, 30
		// 5 : 50
		// 10 20 1 2 3 4
		// 0, 10
		// 0, 10, 20
		// 0, 1, 20
		// 0, 1, 2
		// 0, 1, 2
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int arr[] = new int[N];
		answer = new ArrayList<>();
		
		// list 패딩
		answer.add(0);
		String[] temp = br.readLine().split(" ");
		
		for (int i = 0; i < arr.length; i++) {
			int value = Integer.parseInt(temp[i]);
			
			// 만든 수열의 가장 큰 값보다 클 경우 뒤에 add
			if(answer.get(answer.size()-1) < value) {
				answer.add(value);
				continue;
			}
			
			int s = 0;
			int e = answer.size() - 1;
			
			int index = 0;
			while(s <= e) {
				int mid = (s + e) >> 1;
			
				if(check(mid, value)) {
					index = mid;
					e = mid - 1;
				}else {
					s = mid + 1;
				}
			}
			answer.set(index, value);
		}
		
		System.out.println(answer.size()-1);
	}
	private static boolean check(int mid, int value) {
		return answer.get(mid) >= value;
	}

}

 

<배열을 활용한 소스코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static int[] answer;
	public static void main(String[] args) throws IOException {
		// 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)
		// Ai (1 ≤ Ai ≤ 1,000,000)
		// NlogN의 시간 복잡도를 가져야 함
		
		// 10 20 10 30 20 50 
		// 1  2  1  3  2  4
		// 이진탐색을 활용해서 풀어보자
		// 단절이 발생하는가
		// 1. 특정 수를 선택
		// 2. 그 수 보다 낮으면서 누적 횟수가 가장 많은 경우 + 1
		// 3. 단절성이 있어야 함, 순서대로 탐색을 해도 무방해야 함.
		// 10 20 10 15 20 30 30 50
		// 1  2  1  2  3  4  4  5
		// 1 : 10, 10
		// 2 : 15, 20
		// 3 : 20
		// 4 : 30, 30
		// 5 : 50
		// 10 20 1 2 3 4
		// 0, 10
		// 0, 10, 20
		// 0, 1, 20
		// 0, 1, 2
		// 0, 1, 2
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		answer = new int[N+1];
		
		// list 패딩
		String[] temp = br.readLine().split(" ");
		int lastIndex = 1;
		for (int i = 0; i < N; i++) {
			int value = Integer.parseInt(temp[i]);
			
			// 만든 수열의 가장 큰 값보다 클 경우 뒤에 add
			if(answer[lastIndex-1] < value) {
				answer[lastIndex++] = value;
				continue;
			}
			
			int s = 0;
			int e = lastIndex-1;
			
			int index = 0;
			while(s <= e) {
				int mid = (s + e) >> 1;
			
				if(check(mid, value)) {
					index = mid;
					e = mid - 1;
				}else {
					s = mid + 1;
				}
			}
			answer[index] = value;
		}
		
		
		System.out.println(lastIndex-1);
	}
	private static boolean check(int mid, int value) {
		return answer[mid] >= value;
	}

}