[백준/JAVA] 14003번: 가장 긴 증가하는 부분 수열 5

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, maxLen;
    static int B[] = new int[1000001];     // 현재 가장 유리한 증가 수열 저장
    static int A[] = new int[1000001];     // 수열 데이터 저장
    static int D[] = new int[1000001];     // 0 ~ i까지 i를 포함하는 최장 증가 수열 길이 저장
    static int ans[] = new int[1000000];   // 정답 수열 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int idx;
        B[++maxLen] = A[1];
        D[1] = 1;
        
        for(int i = 2 ; i <= N ; i++) {
            // 가장 마지막 수열보다 현재 수열이 클 때
            if(B[maxLen] < A[i]) {
                B[++maxLen] = A[i]; // B 배열 끝에 A[i] 값 추가
                D[i] = maxLen;
            }
            else {
                // B 배열에서 data[i]보다 첨으로 크거나 같아지는 원소의 idx 찾기
                idx = binarySearch(1, maxLen, A[i]);
                B[idx] = A[i];  // 현재 수열 값 저장
                D[i] = idx;
            }
        }
        
        System.out.println(maxLen); // 가장 긴 증가하는 부분의 수열 길이 출력
        idx = maxLen;
        
        // 뒤에서부터 탐색하면서 정답 수열 저장
        int x = B[maxLen] + 1;
        for(int i = N ; i >= 1 ; i--) {
            if(D[i] == idx && A[i] < x) {
                ans[idx] = A[i];
                x = A[i];
                idx--;
            }   
        }
        
        // 저장된 정답 배열 출력
        for(int i = 1 ; i <= maxLen ; i++) {
            System.out.print(ans[i] + " ");
        }
    }
    
    // 이분탐색 : 현재 수열이 들어갈 수 있는 위치 빠르게 찾기
    static int binarySearch(int l, int r, int now) {
        int mid;
        
        while(l < r) {
            mid = (l + r) / 2;
            if(B[mid] < now)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }    
}

✅ 해결 아이디어
✔ 이분 탐색을 이용한 LIS 구하기 ! 
- 시간 복잡도 : O(N log N) (∵ 수열 크기)

 

데이터 개수가 많아서 DP방식은 시간이 오래 걸려 사용하지 못하고 O(N^2),

이분 탐색을 사용하는 것이라 함

 

설명은.. 나보다 다른 분들이 더 잘해주시니까..

그거 보고 이해할 수 있었다..

 

 

💥 유의사항

: 이분 탐색에 의해 만들어진 리스트가 LIS를 구성하는 요소들은 아님

 

---

🔺 다른 풀이들

- 과정 설명 덕분에 이해가 되었다..ㅠㅠㅠ

[백준 14003] 가장 긴 증가하는 부분 수열 5 (JAVA)

 

- 배열 대신 리스트와 스택을 활용하셨다. 복습할 때 코드는 셋 중 하나로  연습해야곘따

[백준 14003: JAVA] 가장 긴 증가하는 부분 수열 5/ 이분 탐색+ 역추적

[BOJ 백준] 가장 긴 증가하는 수열5 (14003) Java

[java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1

---

💬 느낀 점

처음에 모지... 싶었는데 잘 설명해주신 다른 분들 덕분에 이해할 수 있었다....

압도적 감사....

 

 

보니까 시리즈 문제들도 있던데 얘네도 풀면서 익숙해져봐야겠다!

 

1회독	2회독	3회독	4회독	5회독
V	7/10

 

 

(+7/10 2회독)

우왕 모르겠다... 아래 글 참고했다

[BOJ 백준] 가장 긴 증가하는 수열5 (14003) Java

이 문제 시리즈 아직도 안 풀어봐서 얘네 이번엔 진짜 풀어봐야겠다

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] input, index;   // index[1] : input[1]가 LIS에 들어간 위치
    static ArrayList<Integer> LIS;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        N = Integer.parseInt(br.readLine());
        input = new int[N + 1];
        index = new int[N + 1];
        LIS = new ArrayList<Integer>();
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        
        if(N == 1) { // N이 1이면 바로 끝내기
            bw.write("1\n" + input[1]);
            bw.flush();
            bw.close();
            br.close();
            return;
        }
        
        LIS.add(input[1]);
        index[1] = 0;
        
        // 2. 이진탐색을 활용한 LIS 배열 만들기 🔔
        for(int i = 2 ; i <= N ; i++) {
            if(input[i] > LIS.get(LIS.size() - 1)) {    // 값이 더 큰 경우
                LIS.add(input[i]);
                index[i] = LIS.size() - 1;
            }
            else {
                binarySearch(i);
            }
        }
        
        // 3. 정답 출력
        StringBuilder sb = new StringBuilder();
        sb.append(LIS.size() + "\n");
        
        // 💥 역추적 경로 저장할 Stack
        Stack<Integer> stack = new Stack();
        
        int findId = LIS.size() - 1;
        for(int i = N ; findId >= 0 && i > 0 ; i--) {
            if(index[i] == findId) { // 찾길 원하는 인덱스와 같은 경우,
                findId--; // 찾길 원하는 인덱스 하나 감소시키고
               stack.push(input[i]); // 스택에 경로 추가 (다음 인덱스 값을 찾기 위해)
            }
        }
        
        while(!stack.isEmpty()) { // 스택에서 꺼내며 탐색
            sb.append(stack.pop()).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    
    private static void binarySearch(int id) {
        int start, end, mid;
        start = 0;
        end = LIS.size() - 1;
        
        while(start < end) {
            mid = (start + end) / 2;
            // 값이 더 크면, lower bound 로직
            if(LIS.get(mid) >= input[id]) {
                end = mid;
            }
            else {
                start = mid + 1;
            }
        }
        
        // LIS 배열 갱신하고, 위치 기록
        LIS.set(start, input[id]);
        index[id] = start; // 리스트에 자신의 위치 기록
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편