BOJ(백준 온라인 저지) 14003번 with 자바[JAVA]

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

---

2024.07.03 - [자바[JAVA]/자바[JAVA] 백준] - BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]

BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]

에서 사용했던 LIS 알고리즘을 이용하면 쉽게 풀 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> index = new ArrayList<>();
        ArrayList<Integer> lis = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            list.add(Integer.parseInt(st.nextToken()));
        }

        for (Integer integer : list) {
            int n = Collections.binarySearch(lis, integer);
            // n 이 0 보다 작으면 lis 에 해당 값이 없다는 의미
            if (n < 0) {
                int idx = -1 * n - 1;
                // lis 의 마지막보다 작은 경우 교체를 해주고
                // remove() 하고 add() 하면 ArrayList 특성상 한 번의 수행에 O(N)이 소모된다.
                // 따라서 set() 을 사용한다.
                if (!lis.isEmpty() && integer <= lis.get(lis.size() - 1))
                    lis.set(idx, integer);
                // 아닌 경우는 그냥 추가만 해준다.
                else
                    lis.add(idx, integer);
                index.add(idx);
            }
            // n 이 0 보다 크면 lis 에 해당 값이 이미 존재한다는 의미
            // 이때 lis.set() 이나 lis.add() 는 불필요하므로
            // 그냥 index 만 추가해준다.
            else{
                index.add(n);
            }
        }

        System.out.println(lis.size());
        int lisSize = lis.size() - 1;
        ArrayList<Integer> ans = new ArrayList<>();

        for(int i=index.size()-1; i>=0; i--){
            if(index.get(i) == lisSize) {
                ans.add(list.get(i));
                lisSize--;
            }
        }

        StringBuilder buffer = new StringBuilder();
        for(int i=ans.size()-1; i>=0; i--){
            buffer.append(ans.get(i)).append(" ");
        }

        System.out.println(buffer);
    }
}

 

배움

 

LIS 알고리즘 사용