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

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

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

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제를 풀기 전에 가장 긴 증가하는 부분 수열(LIS)에 대해 모르고 있다면, 아래 문제를 먼저 풀면서 접해보는 것을 권장한다.

 

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

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

 

 

 

 

 

위 11053번 문제와 같이 LIS 길이를 구하는 것은 똑같다.

 

그렇다고 위 문제에서 작성한 코드를 그대로 제출하면 시간초과가 발생할 것이다. 그도 그럴 것이 시간 제한은 같음에도 입력받는 배열의 길이부터가 다르다.

 

 

그렇다면 이 문제를 어떻게 접근해야 할까..?

 

 

우리가 수학적으로 말고 한 번 눈으로 보고 다음 예제에서 증가하는 부분수열을 만들어보자.

{10, 20, 30, 15, 20, 30, 50, 40, 45 ,60}

 

 

어떻게 답이 나왔는가?

 

{10, 15, 20, 30, 40, 45, 60} 이 나왔을 것이다.

자. 여기서 여러분들은 위 수열을 어떻게 풀었는가? 

 

아마 앞에서부터 하나씩 넣어보면서 '직전 숫자 대비 차이가 작은 값' 위주로 넣어보았을 것이다.

 

예로들어 위 수열의 앞부분인 {10, 20, 30}을 먼저 해보다가 중간의 10, 15, 20을 보고 앞의 수열 대신 {10, 15, 20, 30 ... } 이런 식으로 구성했을 것이다.

 

 

한 번 생각해보자. 

LIS, 즉 가장 긴 증가하는 부분 수열이라함은 결국 중점이 '증가' 한다는 것과 '가장 길다' 는 것이다.

 

증가한다는 것은 선행 원소보다 후행 원소가 커야한다는 것이고, 가장 길다는 것은 제한 된 수의 범위 내 볼 때 상호 원소간 값의 차이가 적어야한다는 의미다.

 

 

그럼 한 번 위 예시를 다시 갖고와서 살펴보자.

{10, 20, 30, 15, 20, 30, 50, 40, 45 ,60}

 

맨 처음 LIS배열이 있다고 가정하고 {10} 이 초기상태라고 본다면, 그 다음 원소부터 탐색해나가면 되겠다.

 

20은 10보다 크므로 LIS{10} 에 20을 추가하면 된다.  ---> LIS{10, 20}

마찬가지로 30도 20보다 크므로 LIS에 추가하면 될 것이다.   ---> LIS{10, 20, 30}

 

여기서부터 이제 중요하다.

15는 어떻게해야 할까? 분명 선행 원소인 30 보다는 크지 않다.

그러나 앞서 필자가 두 가지 키워드를 말했었다. 그 중 하나가 바로 상호 원소간 값의 차이가 적어야한다는 것이다. 그래야 최대한 많이 배치할 수 있으니깐 말이다.

 

그럼 어떻게 해야할까?

바로 좀 더 작은 값으로 큰 값을 대치하는 것이다. 좀 더 풀어서 말하면 탐색 값보다 큰 값중 가장 가까이에 있는 수와 맞바꾼다는 것이다.

위 예시에서 본다면 {10, 20, 30} 중에 20을 15로 대치 해볼 수 있겠다.

 

그러면 LIS{10, 15, 30} 상태가 될 것이다. (왜 추가가 아닌 대치하는 것인지는 이후 말씀드리겠다.)

 

그 다음 수열 원소는 20이다. 이도 마찬가지로 LIS의 가장 큰 값인 30보다는 크지 않기 때문에 두 번째 조건으로 가서 수의 간격이 최소화 되도록 해야한다.

20보다 크면서 가장 가까이에 있는 값은 30이니 30을 대체하게 되면 다음과 같겠다. LIS{10, 15, 20}

이런식으로 프로세스를 거치면 다음과 같이 된다.

 

seq={10, 20, 30, 15, 20, 30, 50, 40, 45 ,60}

 

LIS	탐색값	추가/대치	결과
{10}	20	추가	{10, 20}
{10, 20}	30	추가	{10, 20, 30}
{10, 20, 30}	15	대치	{10, 15, 30}
{10, 15, 30}	20	대치	{10, 15, 20}
{10, 15, 20}	30	추가	{10, 15, 20, 30}
{10, 15, 20, 30}	50	추가	{10, 15, 20, 30, 50}
{10, 15, 20, 30, 50}	40	대치	{10, 15, 20, 30, 40}
{10, 15, 20, 30, 40}	45	추가	{10, 15, 20, 30, 40, 45}
{10, 15, 20, 30, 40, 45}	60	추가	{10, 15, 20, 30, 40, 45, 60}

 

 

그러면 이분탐색이 어디에 쓰이는지 감이 오실 것이다.

 

바로, 대치를 하는 과정에 탐색하는 값보다 큰 가장 가까운 원소를 찾는데 쓰인다는 것이다.

 

대략적으로 코드로 짜본다면 다음과 같이 되겠다.

 

for(int i = 1; i < seq.length; i++) {

    // 만약 현재 탐색 값이 LIS의 마지막 값보다 크다면 LIS에 원소 추가
    if(seq[i] > LIS[LastIndex]) {
        LIS.add(seq[i]);
    }
    
    else {
    
        key = seq[i]
        // seq[i]보다 큰 가장 가까운 값을 LIS 찾기위해 lower-bound를 쓴다.
        replaceIndex = lowerBound(LIS, key);
        
        // 대체 할 인덱스에 key(seq[i]) 값으로 대체한다.
        LIS[replaceIndex] = key;
    }
}

 

 

이런 식으로 작성을 하면 된다.

 

 

마지막으로, 왜 추가가 아닌 대치하는 것인지는 이후 말씀드리겠다는 것에 답하는 것만 남았다.

 

 

먼저 중요한 것은 위 예제 과정에서도 보았겠지만, 실제로는 LIS를 만족하지 않는 상태가 될 수도 있다.

예로들어 seq={10, 20, 30, 15} 만 주어진다고 해보자.

 

만약 위 과정대로라면 LIS는 {10, 15, 30} 이 나오겠지만, 실제 LIS는 {10, 20, 30} 이다. 그래서 만약 문제에서 LIS를 출력하라고 하면 틀릴 것이다.

 

근데 왜 위와 같은 방식이 가능한 것인가.

 

 

문제에 대해 파악해 볼 필요가 있는데, 우리가 구하고자 하는 것은 '길이' 이다.

 

즉, 안의 내용물은 출력과는 관련이 없고 단순히 우리가 '최대한 많이 배치할 수 있도록' 하기 위한 배치가 될 뿐이다.

쉽게 말해 좀 더 작은 값으로 대치하여 이후 원소가 더 많이 들어 올 수 있는 가능성을 넓히는 과정이라고 봐도 된다.

 

 

seq={10, 20, 30, 15, 20, 30, 50, 40, 45 ,60}

{10, 15, 20, 30, 50} 상태일 때, 만약 50을 40으로 대치해주지 않았다면, 45는 들어올 수 없었을 것이다. 

 

만약에 주어진 수열이 seq={10, 20, 30, 15, 20, 30, 50, 40} 까지라 하더라도 {10, 15, 20, 30, 50} 이나, {10, 15, 20, 30, 40} 이나 값이 대치 된 것일 뿐 길이에 영향을 주는 것이 아니다.

 

그렇기 때문에 어디까지나 '길이'를 구하는데 한정하여 이분탐색을 활용해 풀이 할 수 있다는 것이다.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

입력 방식의 차이를 두어 풀이해보도록 하겠다.

 

 

1. Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		int[] seq = new int[N];
		int[] LIS = new int[N];


		for (int i = 0; i < N; i++) {
			seq[i] = in.nextInt();
		}

		// LIS 초기 값으로 첫 번째 수열의 값을 갖는다.
		LIS[0] = seq[0];
		int lengthOfLIS = 1;
		
		for (int i = 1; i < N; i++) {

			int key = seq[i];
			
			// 만약 key가 LIS의 마지막 값보다 클 경우 추가해준다. 
			if (LIS[lengthOfLIS - 1] < key) {
				lengthOfLIS++;
				LIS[lengthOfLIS - 1] = key;
			} 
			else {
				// Lower Bound 이분탐색을 진행한다.
				int lo = 0;
				int hi = lengthOfLIS;
				while (lo < hi) {
					int mid = (lo + hi) / 2;
					
					if(LIS[mid] < key) {
						lo = mid + 1;
					}
					else {
						hi = mid;
					}

				}
				/*
				 *  lo가 LIS에서 대치 될 원소의 위치가 될 것이고
				 *  해당 위치에 key값으로 원소를 바꿔준다.
				 */
				
				LIS[lo] = key;
			
			}
			
		}
		// 위 과정을 통해 나온 LIS의 길이를 출력한다.
		System.out.println(lengthOfLIS);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

코드 자체는 그동안 배워왔던 이분 탐색에서 크게 벗어나지 않는 내용이라 큰 무리 없이 이해하실 수 있을 것이다.

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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 IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] seq = new int[N];
		int[] LIS = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}

		// LIS 초기 값으로 첫 번째 수열의 값을 갖는다.
		LIS[0] = seq[0];
		int lengthOfLIS = 1;
		
		for (int i = 1; i < N; i++) {

			int key = seq[i];
			
			// 만약 key가 LIS의 마지막 값보다 클 경우 추가해준다. 
			if (LIS[lengthOfLIS - 1] < key) {
				lengthOfLIS++;
				LIS[lengthOfLIS - 1] = key;
			} 
			else {
				// Lower Bound 이분탐색을 진행한다.
				int lo = 0;
				int hi = lengthOfLIS;
				while (lo < hi) {
					int mid = (lo + hi) >>> 1;
					
					if(LIS[mid] < key) {
						lo = mid + 1;
					}
					else {
						hi = mid;
					}

				}
				/*
				 *  lo가 LIS에서 대치 될 원소의 위치가 될 것이고
				 *  해당 위치에 key값으로 원소를 바꿔준다.
				 */
				
				LIS[lo] = key;
			
			}
			
		}
		// 위 과정을 통해 나온 LIS의 길이를 출력한다.
		System.out.println(lengthOfLIS);
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 42427589  -  방법 2 : BufferedReader

채점 번호 : 42427577  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제는 만약 기존에 이러한 유형을 접해본 것이 아니라면 확실히 아이디어가 바로 떠오르는 문제는 아닌 것 같다. 막상 코드로 보면 별 것 아니긴 해도 우리가 LIS를 구하는 방식에 관성적으로 접근하게 되어 값을 대치한다는 것을 바로 떠오르기는 어렵지 않았을까 싶다.

 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.

 

이로써 이분탐색 파트는 끝났다.

 

여담으로 근래 포스팅 업로드 주기가 빠르지 못해 죄송하다. 더군다나 근래 보니 누적 합이라는 카테고리가 생겨 해당 카테고리부터 다시 한 번 훑고 가야할 것 같다.