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

 

 

 

🧫 문제 분석

 

✔️ 출처

가장 긴 증가하는 부분 수열 2 골드 2

 

📖 문제

 

가장 긴 증가하는 부분 수열 1에 이어 2문제는 DP로는 불가능하고

이분탐색을 통한 대치, 추가를 하여 부분 수열을 만들어 가야한다. 

 

많은 블로그들이 원리를 설명하고 있으므로 생략하고

 

내가 헷갈렸던 것만 정리한다. 

 

범위 탐색에서 front <= back, front < back을 많이 사용하는데 언제 사용하는지 몰라서 

무분별하게 front <= back을 사용했는데 

 

이문제는 이렇게 풀면 좋지 않다.  근데 이렇게 해서 풀긴했다... ㅋㅋ

 

front <= back은 정확한 값을 탐색할때 사용하는 것이 좋다. 

이유는 front == back일때도 탐색함으로써 정확한 탐색이 가능하기 때문이다. 

 

front < back은 탐색 범위를 줄여 최적의 위치를 찾을 때 사용한다. 

front = mid + 1;

back = mid; 

이런식으로 범위를 줄이는데

 

현재 mid 위치의 값 < 탐색하는 값 일때 

front는 mid + 1을 하는 이유가 뭘까 라는 의문점이 생겼다.

 

LIS는 증가하는 부분 수열이다.  mid 에 있는 값보다  더 크다면 mid를 제외한 더 큰 범위에서 자신의 적정 위치를 찾으면 되므로 mid를 탐색범위에 넣을 필요가 없다.

 

즉, 현재 mid 값보다 더 큰 값 중에서 적절한 위치를 찾아야한다. 

 

현재 mid 위치 값 >= 탐색하는 값 일때

back = mid를 하는 이유는 mid도 탐색 범위이기 때문이다. 

'mid의 위치값이 탐색하는 값과 같을때' 이것 떄문인 것 같다. 

 

 

 

---

🔅 문제 풀이

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] sequence = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        sequence[0] = Integer.parseInt(st.nextToken());
        int size = 1;

        for (int i = 1; i < n; i++) {
            int num =  Integer.parseInt(st.nextToken());
            int front = 0, back = size - 1;

            if (sequence[back] < num) {
                sequence[size++] = num;
                continue;
            }

            while (front <= back) {
                int mid = (front + back) / 2;

                // 수열에 mid 위치에 값이 num 보다 크다면
                if (sequence[mid] > num) {
                    back = mid - 1;

                } else if (sequence[mid] < num){
                    front = mid + 1;
                } else {
                    break;
                }

                if (front > back) {
                    if (sequence[mid] > num) {
                        sequence[mid] = num;

                    } else {
                        sequence[front] = num;
                        size += front == size ? 1 : 0;
                    }
                }
            }
        }

        bw.write(size + "");
        bw.flush();
        bw.close();
    }
}

 

🔅 배운대로 해보기 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] sequence = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        sequence[0] = Integer.parseInt(st.nextToken());
        int size = 1;

        for (int i = 1; i < n; i++) {
            int num =  Integer.parseInt(st.nextToken());

            // 마지막 것보다 크다면 맨 뒤에 추가
            if (sequence[size - 1] < num) {
                sequence[size++] = num;
                continue;
            }

            int front = 0, back = size;

            while (front < back) {
                int mid = (front + back) / 2;

                if (sequence[mid] < num){
                    front = mid + 1; // mid를 포함하지 않은 오른쪽 탐색
                } else {
                    back = mid; // mid 를 포함한 왼쪽 탐색
                }
            }
            sequence[front] = num;
        }

        bw.write(size + "");
        bw.flush();
        bw.close();
    }
}

 

❗ 오답노트 / 필요한 지식

1.  더 많이 풀어보고 익히자.