[BaekJoon] 3745 오름세 (Java)

1.  문제 링크

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

2.  문제

요약

• 정인이는 주가의 오름세를 살펴보려고 하는데, n일 동안 매일 주가를 적어놓았고, 거기서 오름세를 찾으려고 합니다.
• n일 동안의 주가를 $p_{i_1}, p_{i_2}, ..., p_n$이라고 할 때, 오름세란 부분수열 $p_{i_1} < p_{i_2} < ... < p{i_k} (i_1 < i_2< ... <i_k)$을 말합니다.
• n일 동안의 주가가 주어졌을 때, 가장 긴 오름세를 찾는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수가 주어집니다. 각 테스트 케이스의 첫 번째 줄에 100,000보다 작거나 같은 주가를 관찰한 날의 수 N이 주어지고 두 번째 줄에 관찰한 첫 날부터의 주가가 순서대로 주어집니다. 주가는 100,000보다 작거나 같은 자연수입니다.
• 출력: 각 테스트 케이스에 대해 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] stocks;

    static void solution() {
        ArrayList<Integer> subsequence = new ArrayList<>();
        subsequence.add(0);

        for(int idx = 0; idx < N; idx++) {
            if(subsequence.get(subsequence.size() - 1) < stocks[idx])
                subsequence.add(stocks[idx]);
            else {
                int index = binarySearch(0, subsequence.size() - 1, stocks[idx], subsequence);
                subsequence.set(index, stocks[idx]);
            }
        }

        sb.append(subsequence.size() - 1 == 0 ? 1 : subsequence.size() - 1).append('\n');
    }

    static int binarySearch(int left, int right, int objective, ArrayList<Integer> subsequence) {
        int mid = 0;
        while(left < right) {
            mid = (left + right) / 2;
            if(subsequence.get(mid) < objective) left = mid + 1;
            else right = mid;
        }

        return right;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = null;

        while((inputStr = br.readLine()) != null) {
            N = Integer.parseInt(inputStr.trim());
            stocks = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int idx = 0; idx < N; idx++)
                stocks[idx] = Integer.parseInt(st.nextToken());

            solution();
        }

        System.out.print(sb);
    }
}

4.  접근

• 오름세는 인덱스가 증가할수록 주가가 올라가는 부분수열을 뜻하는데, 이는 LIS를 구하는 것과 마찬가지입니다.
• 그러므로 이분탐색을 이용하여 LIS의 길이를 구하는 방식으로 문제를 해결합니다.

• stocks라는 배열에 주어진 주가 정보들을 넣고 LIS를 나타내는 수를 넣기 위해 subsequence라는 ArrayList를 생성합니다.
  • subsequence에는 0을 먼저 넣어 초기화합니다.
• 주어진 주가 정보들을 차례대로 순회하면서 LIS를 찾습니다.
  • 만약 현재 주가가 subseuqnece에서의 가장 마지막 수, 즉 LIS에서 가장 큰 수보다 크다면 LIS에 해당될 수 있으므로 subsequence에 현재 주가를 넣습니다.
  • LIS에서 가장 큰 수보다 작거나 같다면 이분 탐색을 통해 현재 주가로 변경할 적절한 인덱스를 찾고 해당 인덱스의 값을 현재 주가로 변경합니다.
• 처음에 0을 넣고 시작하였기 때문에 전체 LIS 길이는 (subsequence의 길이 - 1)이 될 것인데, 만약 (subsequence의 길이 - 1)가 0이라면, LIS에 최소 하나의 수는 들어가기 때문에 1로 변환합니다.