11501 주식

자바 / 실2 / 그리디 알고리즘

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

 

문제 이해

 

홍준이가 할 수 있는 행동

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

ex) 3 5 9의 경우, 첫 번째와 두 번째 날 주식을 하나씩 산다 (-3-5 = -8)

세 번째 날, 가지고 있던 주식 두 개를 9원에 판다 (9x2 = 18)

최종 이익: -8 + 18 = 10

ex) 1 1 3 1 2 의 경우

첫 번째와 두 번째 날 주식을 하나 씩 산다 (-1-1 = -2)

세 번째 날, 가지고 있던 주식 두 개를 3원에 판다 (3x2 = 6)

네 번째 날, 주식을 하나 산다 (-1)

마지막 날, 가지고 있던 주식 한 개를 2원에 판다 (2x1 = 2)

최종 이익: -2 + 6 -1 + 2 = 5

 

그리디 알고리즘은 매 순간 최적의 해를 선택하는 알고리즘 풀이 방법이다. 

이 경우, 각 날마다 홍준이가 할 수 있는 행동들 중 최선의 선택을 하면 된다. 

 

나의 알고리즘은 이렇다: 앞으로 남은 날 들 중에, 오늘보다 주가가 비싼 날이 있는 경우 주식을 구매하고, 없는 경우 주식을 구매하지 않는다. 앞으로 남은 날 들의 주가가 오늘과 전부 같은 경우, 3번 아무것도 안한다를 선택한다.

 

세상... 시간초과 때문에 너무 애를 먹었다. 시간복잡도 적게 (즉 코드를 효율적으로) 짜는 연습이 많이 부족한 것 같다.

 

다음은 시간초과가 난 코드이다. 87%에서 시간초과가 났으니 아마 내 생각엔 답은 맞는 듯 하다.

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

public class Main
{
    private static int T, N, num = 0, mxidx;
    private static long sum = 0;
    private static int[] array;

    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++)
        {
            sum = 0;
            num = 0;
            mxidx = 0;
            N = Integer.parseInt(br.readLine());
            array = new int[N];
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            for(int j = 0; j < N; j++)
            {
                array[j] = Integer.parseInt(st.nextToken());
            }
            mxidx = where_is_max(0);
            for(int j = 0; j < N; j++)
            {
                if (mxidx == 0)
                {
                    mxidx = where_is_max(j + 1);
                }
                else if (j == mxidx)
                {
                    sum += num * array[j];
                    mxidx = where_is_max(j + 1);
                    num = 0;
                }
                else
                {
                    num++; 
                    sum -= array[j];
                }
            }
            System.out.println(sum);
        }
    }
    
    private static int where_is_max(int stidx)
    {
        int max = 0, index = 0;
        for(int i = stidx; i < N; i++)
        {
            if (max < array[i])
            {
                max = array[i];
                index = i;
            }
        }
        return index;
    }
}

단순하게, 맨 처음 mxidx에 array의 가장 큰 수의 인덱스를 넣어놓고, 그 가장 큰 수가 나올 때까지 구매만 진행한다.

가장 큰 수가 나왔다면, 그 다음 where_is_max함수에 매개변수로 현재 위치 + 1 인덱스를 넣어주어 현재 위치 다음부터 가장 큰 값을 갖는 인덱스를 찾아 같은방식으로 진행하는 알고리즘이었다.

시간복잡도를 고려하지 않고 푼 방식이었고, 예상대로 시간초과가 났다.

 

다음으로 시간초과를 고려한 알고리즘을 생각해봤다.

정말 많이 헤멨다. 덱을 사용했다가, 배열을 사용했다가... 뭐가 되는 것 같아서 막 해보다가 반례를 하나 찾아 그걸 해결하려고 보니 시간복잡도가 또 nxn이라던가... ㅜㅜ 힘들었다

 

최종 알고리즘

배열이 내림차순이 되도록 순서를 갖는 인덱스 배열을 만드는 것이었다.

무슨 말이냐면, 만약 배열이 {3 2 5 1 9}라면, {4 2 0 1 3}값을 갖는 idx라는 배열을 만들었다.

// idx 배열 선언 및 초기화
            Integer[] idx = new Integer[N];
            for(int j = 0; j < N; j++)
            {
                idx[j] = j;
            }

//정렬
            Arrays.sort(idx, new Comparator<Integer>()
            {
                public int compare(Integer i1, Integer i2)
                {
                    return Integer.compare(array[i2], array[i1]);
                }
            });

아직 자바의 comparator의 사용에 익숙지 않아 지피티의 힘을 빌렸다. 추후 공부하여 업로드 할 예정이다.

 

다음이 주요 알고리즘 코드이다.

            for(int j = 0; j < N; j++)
            {
                if (j == idx[k]) 
                {
                    sell = idx[k];
                    sum += num * array[j];
                    num = 0;
                    while(idx[k] <= sell && k < N - 1)
                    {
                        k++;
                    }
                }
                else 
                {
                    num++; 
                    sum -= array[j];
                }
            }

idx[k] 값이 파는 시점이므로, idx[k]와 array의 인덱스인 j가 같아지는 순간 판매하고, (가진 개수 초기화, 총 이익 올리기)

판매한 시점의 인덱스보다 인덱스가 커질 때 판매해야 하므로 그 시점까지 k를 올리는 방식으로 구현했다.

 

다음은 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;

public class Main
{
    private static int T, N, num = 0;
    private static long sum = 0;
    private static int[] array;

    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++)
        {
            int k = 0;
            int sell = 0;
            sum = 0;
            num = 0;
            N = Integer.parseInt(br.readLine());
            array = new int[N];
            Integer[] idx = new Integer[N];
            for(int j = 0; j < N; j++)
            {
                idx[j] = j;
            }
            
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            for(int j = 0; j < N; j++)
            {
                array[j] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(idx, new Comparator<Integer>()
            {
                public int compare(Integer i1, Integer i2)
                {
                    return Integer.compare(array[i2], array[i1]);
                }
            });

            for(int j = 0; j < N; j++)
            {
                if (j == idx[k]) 
                {
                    sell = idx[k];
                    sum += num * array[j];
                    num = 0;
                    while(idx[k] <= sell && k < N - 1)
                    {
                        k++;
                    }
                }
                else 
                {
                    num++; 
                    sum -= array[j];
                }
            }
            
            System.out.println(sum);
        }
    }

}

 

 

다음은 내가 참고했던 여러 반례들이다.

1
9
8 5 3 8 10 7 5 5 2 

답: 16

1
4
10 9 4 5

답: 1

1
3
2 1 2
답: 1

1
4
9 8 9 7
답: 1

1
5
1 3 2 5 4
답: 9

1
5
1 2 10 1 2
답: 18

1
5
5 3 2 10 14
답: 23

1
4
1 2 1 5
답: 11