[이진 탐색] 백준 12014 주식 자바 (Java)

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

12014번: 주식

 

문제

어느 날 당신은 출근길에, 지하철역 쓰레기통에서 놀라운 문서를 얻게 되었다. 이 문서는 미래의 어떤 회사의 주식 가격의 변동이 담겨 있었다. 설마 하는 마음으로 이 회사의 주식 가격의 변동을 본 결과, 문서에 담긴 내용이 사실이라는 것을 알게 되었다. 아마도 미래에서 타임머신을 타고 온 후손이 선조를 돕기 위해서 보낸 것이 아닐까 하는 마음이 들었다.

앞으로 N 일간 주식 가격이 N 개의 숫자로 주어져 있다. 당신은 지금까지 주식이라는 것을 거래해본 적이 없기 대문에, 증권회사에 가서 거래를 시작하기로 했다. 미래를 알면서 주식을 거래한다면 다른 사람들이 의심할지도 모른다는 생각이 들어서, 총 K 번 주식을 사기로 했다. 하루에는 주식을 한 번만 살수 있기 때문에, 주식을 사는 날은 총 K 일이다.

의심을 더 줄이기 위해서, 주식을 살 때마다 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사기로 했다. 예를 들어, 10일간 주가의 변동이 다음 표와 같다고 하자.

K=3이라면, 2일, 3일, 4일에 주식을 사면 그날의 주가는 50, 70, 90이기 대문에 주어진 조건을 만족한다. 만약 K=6이라면, 2일, 3일, 5일, 6일, 7일, 9일에 주식을 사면 주가가 50, 70, 75, 87, 105, 110이기 때문에 주어진 조건을 만족한다. K=10이라면 조건을 만족할 수 없다.

N과 K, 주가가 주어졌을때 주어진 조건을 만족하게 주식을 구입할 수 있는지 여부를 알려주는 프로그램을 작성하시오.

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 정수 N과 K이 주어진다. N은 앞으로 주가를 알 수 있는 날 수이며, (1 ≤ N ≤ 10,000) K는 거래의 회수이다. (1 ≤ K ≤ 10,000) 다음 줄에는 앞으로 N 날의 주가가 사이에 공백을 두고 주어진다. 주가는 1부터 10,000 사이의 정수이다.

출력

각 테스트 케이스에 대해서 출력은 한 줄로 구성된다. T 번째 테스트 케이스에 대해서는 첫째 줄에는 "Case #T"를 출력한다. 두 번째 줄에는 주어진 조건을 만족하게 주식을 살 수 있으면 1, 아니면 0을 출력한다.

코드

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class No12014 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int i = 0; i < T; i++){
            int N = sc.nextInt();
            int K = sc.nextInt();
            int result = 0;

            int[] arr = new int[N];
            ArrayList<Integer> list = new ArrayList<>(); // 구매한 주식 리스트

            for(int j = 0; j < N; j++) {
                arr[j] = sc.nextInt();
            }

            list.add(arr[0]);
            for(int j = 1; j < N; j++) {
                if (list.get(list.size()-1) < arr[j]){
                    list.add(arr[j]); // 이전 주식 보다 올랐으므로 구매함
                }
                else {
                    int left = 0;
                    int right = list.size() - 1; //리스트는 0부터 시작하므로 -1
                    while ( left <= right){
                        int mid = (left + right) / 2;
                        if (list.get(mid) < arr[j])
                            left = mid + 1;
                        else
                            right = mid - 1;
                    }
                    list.set(left, arr[j]);
                }
            }
            if (list.size() >= K)
                result = 1;
            System.out.println("Case #"+(i+1));
            System.out.println(result);
        }
    }
}

풀이

1일차:70, 2일차:90, 3일차:75, 4일차:85라는 주가가 있을 때 2일차를 구매하면 3~4일차를 구매 할 수 없지만 2일차를 제외하고 구매하면 1, 3, 4일차를 구매 할 수 있기 때문에 더 많이 구매 할 수 있다.

즉, 주가가 마지막 구매 가격 보다 떨어졌다면 이진 탐색하여 값을 갱신하며 구매 할 수 있는 최대 일수를 계산한다.

 

아래와 같은 구매한 리스트가 있다고 할때

마지막 요소보다 큰 값이 들어온다면 맨 뒤에 추가 된다.

마지막 요소보다 작은 값이 들어오게 되면 들어온 값보다 같거나 큰 값중 가장 인접한 값을 대체한다. 

이진 탐색 코드&방법

아래에 있는 링크에 설명되어 있음

https://seaotter.tistory.com/21

[이진 탐색] 이진탐색 방법 & 자바 코드