[Java] BOJ 12014 - 주식

 

 

BOJ 12014 - 주식 (https://www.acmicpc.net/problem/12014)

 

01. 🔎 문제 탐색

1개 회사에 대한 미래 N일간 주식 변동을 가지고 있음
N일간 주식 가격 N개가 주어짐

주어진 주가를 바탕으로 주식을 K번 매수하기로 함
(단, 하루에 1번 매수 가능)

또한, 직전 날에 매수했던 주가보다 높은 주가에 구매해야 함
(매수하는 주가가 점점 상승한다는 말)

N: N일에 대한 주가 N개
K: 희망 거래 횟수

• 주어진 N개의 주가에대해 하루에 한 번 구매한다고 했을 때, 점점 상승하도록 K번 구매할 수 있는 지 여부를 출력

01-1. 알고리즘 선택 & 시간 복잡도

• LIS(최장 증가 부분 수열) 알고리즘으로 점점 증가하도록 수열을 만들었을 때, 그 길이가 K 이상이면 가능한 경우의 수이다.
• 주어진 주가 N에 대해서 1번 탐색하며, 수열의 자리를 이분탐색으로 알 수 있으므로, 시간 복잡도는 $O(N log N)$

02. 📝 코드 설계하기

1. N일에 대한 주가 N개와 희망 매수 횟수 K를 입력
2. 주가를 1부터 N까지 순차적으로, 수열에 들어갈 수 있는 자리를 이분탐색
   1. lowerBound로 탐색하며, 탐색 중인 수와 같거나 큰 수가 없을 경우 list에 추가
   2. 탐색 중인 수와 같거나 큰 수가 최초로 등장시, 그 위치에 새로운 수로 대체
3. list는 LIS에 대한 최대 길이를 나타냄 $\rightarrow$ 따라서, 길이가 K와 같거나 크다면 K번 구매할 수 있다는 의미
   (원소는 다를 수 있음)

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

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

public class Main {
  final static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  final static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  static int N, K;
  static int[] arr;

  public static StringTokenizer input() throws IOException{ 
    return new StringTokenizer(br.readLine()); 
  }

  public static void print(Object o) throws IOException{ 
    String s = String.valueOf(o);
    bw.write(s);
  }

  public static int lowerBound(List<Integer> list, int target){
    int left = 0, right = list.size();
    while(left < right){
      int mid = (left+right)/2;

      if(list.get(mid) < target) left = mid+1;
      else right = mid;
    }

    return left;
  }

  public static int solution() throws IOException{
    List<Integer> stock = new ArrayList<>();
    
    for(int i = 0; i < N; i++){
      int idx = lowerBound(stock, arr[i]);

      if(stock.size() == idx) stock.add(arr[i]);
      else stock.set(idx, arr[i]);
    }

    if(stock.size() >= K) return 1;
    else return 0;
  }

  public static void main(String[] args) throws IOException {
    StringTokenizer st = input();

    int T = Integer.valueOf(st.nextToken());

    for(int i = 0; i < T; i++){
      st = input();
      N = Integer.valueOf(st.nextToken()); 
      K = Integer.valueOf(st.nextToken());
      
      arr = new int[N];

      st = input();
      for(int j = 0; j < N; j++) arr[j] = Integer.valueOf(st.nextToken());

      print("Case #" + (i+1) + "\n");
      print(solution() + "\n");
    }

    
    bw.flush();
    bw.close();
    br.close();
  }
}