백준 12014번 : 주식 [Java]

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

 

문제 탐색하기

문제에서는 아래와 같이 설명이 장황하게 되어있지만 결국 원하는 건 가장 긴 증가하는 수열이다. 

주식을 살 때마다 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사기로 했다.

 

가장 긴 증가하는 수열을 구하는 방법은 두 가지 시간 복잡도로 나눌 수 있는데, 모든 수열을 찾는 O(N^2)이 걸리는 방법과, 하나의 리스트를 사용하여 인덱스를 찾아가며 교환하는 O(NlogN)이 걸리는 방법이 있다. 문제의 최대 입력을 생각해보면 100 * 10000 * 100 = 100억 이므로 시간 제한 5초안에 통과하려면 무조건 O(NlogN)이 걸리는 방법을 사용해야 한다. 

 

O(NlogN)은 이분탐색을 통해서 구하는 방법인데 경계값을 찾는 방법 중 lower bound를 사용한다. lower bound는 현재 값보다 크거나 같은 값을 찾는 알고리즘인데, 위의 알고리즘에서 기록을 하게 되는 리스트에서 경계 값을 찾아서 해당 위치의 값을 바꾸어야 하기 때문에 사용한다. 이에 따라서 매 테스트 케이스마다 첫번째 값을 추가하고 모든 값을 lower bound를 통해서 리스트에 어떤 부분에 추가해야할지 찾아본다. 이 때, 리스트는 정렬된 상태이므로 리스트의 마지막 값보다 크다면 리스트에 그냥 추가하고 그 외의 경우 특정 위치를 변경한다. 

 

이 방법을 통해서 가장 긴 증가하는 수열의 길이를 찾을 수 있다. 문제에서는 가장 긴 증가하는 수열의 길이가 k보다 크거나 같으면 1을 출력하고 그 외의 경우 0을 출력하면 되므로 이를 구현하면 답을 받을 수 있다.

 

코드 구현하기

1. 모든 테스트 케이스 당 아래를 반복한다.
   1. 입력을 처리하고 입력되는 1차원 배열을 저장한다.
   2. 배열을 탐사하면서 기록할 리스트를 만들고 저장된 배열의 0번째 인덱스의 수를 리스트에 추가한다.
   3. 배열을 1번째 인덱스 부터 탐사하며 리스트의 어떤 인덱스에 삽입될지 탐색한다.
   4. 탐색이 끝났다면 리스트의 마지막 인덱스인 수보다 현재 수가 큰지 확인하고 크다면 리스트의 마지막에 추가한다. 그 외의 경우에는 찾은 인덱스의 값보다 현재 값이 작다면 현재 값을 해당 인덱스에 있는 값과 교체한다.
   5. 모든 연산이 끝나면 찾은 리스트의 길이와 k를 비교하여 답을 출력한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
	public static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;

	    public FastReader() {
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    String next() {
	        while (st == null || !st.hasMoreElements()) {
	            try {
	                st = new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        }
	        return st.nextToken();
	    }

	    int nextInt() {
	        return Integer.parseInt(next());
	    }
	}

	static int TC;
	static int[] nums;

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		TC = fr.nextInt();
		for (int i = 0; i < TC; i++) {
			int n = fr.nextInt();
			int k = fr.nextInt();
			nums = new int[n];
			for (int j = 0; j < n; j++) {
				nums[j] = fr.nextInt();
			}

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

			list.add(nums[0]);

			for (int j = 1; j < n; j++) {
				int low = 0;
				int high = list.size() - 1;
				int mid = 0;
				while (low <= high) {
					mid = (low + high) / 2;
					if (nums[j] > list.get(mid)) {
						low = mid + 1;
					} else {
						high = mid - 1;
					}
				}

				if (list.get(list.size() - 1) < nums[j]) {
					list.add(nums[j]);
				} else {
					list.set(low, nums[j]);
				}
			}
			System.out.println("Case #" + (i + 1) + "\n" + (list.size() >= k ? 1 : 0));
		}
	}
}