[Java] 그리디 - 최댓값 갱신 (주식)

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

11501번: 주식

 

 

 

시간 초과에 걸리지 않도록 탐색하는 게 목표인 문제다. 단순하게 생각해서 마구잡이로 for 문을 돌린다면 N의 최댓값 1,000,000인 O(N*N*T)의 말도 안 되는 Time Complexity 때문에 for문 한 번으로 문제를 푸는 방법을 찾아야 한다.

내가 생각한 방법은 객체 배열 ArrayList를 만드는 것이다.

 

1. ArrayList에 주식의 값과 날짜를 받아와 내림차순으로 정렬한다.

2. ArrayList의 첫 번째 index부터 비교해서 만약 그 주식의 날짜가 현재 날짜보다 크다면 무조건 그날 매도.

3. 매도 후 가격을 더함.

 

위 방식처럼 한번 정렬 후 탐색 한다면 비록 for 문을 두 번 돌지만 두 번째 for문에서 최대한 빠르게 break 해 빠져나올 수 있기 때문에 시간 초과에 걸리지 않을 수도 있겠다고 생각했지만, 결국 시간초과에 걸렸다.

아무리 정렬을 한다고 해도 일단 정렬 그 자체와 최댓값의 주식을 산 날짜가 계속 현재보다 빠르다면 for문이 빨리 끝나지 않기 때문인 것 같다.

 

 

class MaxIndex{
    int value;
    int index;

   MaxIndex(int v, int i){
       this.value = v;
       this.index = i;
   }
}

public class Main {
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        long sum=0;
        int T = Integer.parseInt(br.readLine());
        int number; //날짜 수
        int price[]; //주식 가격

        for(int i=0; i<T; i++){
            sum = 0;
            long max=0;
            ArrayList<MaxIndex> array = new ArrayList<>();

            number = Integer.parseInt(br.readLine());

            price = new int[number];
            st = new StringTokenizer(br.readLine());


            for(int j=0; j<number; j++){
                price[j] = Integer.parseInt(st.nextToken());
                array.add( new MaxIndex(price[j],j) );
            }


            Collections.sort(array, new Comparator<MaxIndex>() {
                @Override
                public int compare(MaxIndex o1, MaxIndex o2) {
                    return o2.value - o1.value;
                }
            });


            for(int j=0; j<number; j++){

                for(int k=0; k<number; k++){
                    if(j < array.get(k).index && price[j] < array.get(k).value) { //오름차순으로 정렬되어 있는 arraylist에서 최댓값의 인덱스보다 현재 인덱스가 작아야함
                        sum+= array.get(k).value-price[j];
                        break;
                    }
                }
            }

            sb.append(sum + "\n");

        }

        System.out.println(sb);
    }
}

 

시간 초과난 첫 번째 코드인데 이 문제를 풀면서 객체 ArrayList의 정렬을 어떻게 하는지 알게 되었다.

 

그냥 Collections.sort를 쓸 수 없고 오버라이딩 해야 하는데 위 코드처럼 내가 원하는 변수로 정렬할 수 있다.

추가로 o2.value-o1.value의 순서를 바꿔서 o1.value-o2.value로 한다면 오름차순으로 정렬된다. 

 

중첩 반복문인 경우 break를 사용해 하나의 for 문을 빠져나올 수 있다 (continue는 안 되는 듯)

 

 

 

 

 

정답 코드는 발상의 전환인데  for문을 뒤에서부터 돌리는 방식이다.

가장 뒤에서부터 최댓값을 갱신해 가면서 이전 날의 주가가 최댓값 보다 적거나 같다면 매수하고 그렇지 않다면 최댓값을 갱신해 간다.  

 

 

발상의 전환으로 정말 쉽고 빠르게 풀었다. 왜 for문을 항상 앞에서부터 시작했을까. 가끔은 뒤에서부터 시작해 보는 생각도 해보자.

 

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        long sum=0;
        int T = Integer.parseInt(br.readLine());
        int days; //날짜 수
        int price[]; //주식 가격

        for(int i=0; i<T; i++){
            sum = 0;
            int max=0;

            days = Integer.parseInt(br.readLine());

            price = new int[days];
            st = new StringTokenizer(br.readLine());


            for(int j=0; j<days; j++){
                price[j] = Integer.parseInt(st.nextToken());
            }

            for(int j=days-1; j>=0; j--){

                if(price[j] > max) max = price[j];
                else  sum+= (max-price[j]);
            }

            sb.append(sum + "\n");
        }

        System.out.println(sb);
    }
}