[TopCoder] StockHistory (주식 히스토리)

당신은 최근에 월급 인상과 함께 직장에서 일회성 보너스를 받았습니다. 새로 발견한 돈을 유용하게 사용하기 위해, 당신은 주식 시장에 투자하기로 결정했다. 최근의 시장 기록에 대해 알아보려면 구입에 관심이 있을 수 있는 여러 주식에 대한 과거 데이터를 얻으셨습니다.

실험을 위해 선택한 주식의 잠재적 성과를 평가하려고 합니다. 당신이 궁금해 하는 것은, 만약 당신이 처음에 initialInvestment를 투자 했다면, 얼마나 많은 돈을 벌 수 있었냐는 것이다. 그리고 그 이후 매달 추가적인 monthlyContribution 달러가 있습니다. 매월 초에 주식을 얼마든지 매수할 수 있으며(주식의 소수 포함) 데이터에 표시된 기간이 끝날 때(지난달 초) 보유 주식을 모두 매도한다고 가정합니다. 당신은 중간 기간에 주식을 팔 수 없습니다. (자세한 내용은 예를 참조하십시오.)

각 요소가 월 초에 각 주식의 가격을 나열하는 주가가 제공됩니다. 주가의 각 요소는 "stock0 stock1..."(명확성을 위해 추가된 인용구) 형태이며, 여기서 각 stocki는 선행 0이 없는 양의 정수이다. 주가의 첫 번째 요소는 초기 가격을 제공하고, 두 번째 요소는 투자를 시작한 후 첫 달 초에 가격을 제공합니다.

당신은 기간이 끝날 때까지 당신이 벌 수 있는 최대 수익(이익)을 나타내는 것을 반환해야 한다. 결과를 가장 가까운 정수로 반올림해야 합니다.

Definition

Class:

 

StockHistory

Method:

 

maximumEarnings

Parameters:

 

Returns:

 

int

Method signature:

 

(be sure your method is public)

 

Examples

0)

1000

0

{"10 20 30", "15 24 32"}

Returns: 500

Clearly the first stock is a bigger gain than either of the others. We go all in on it.

1)

1000

0

{"10", "9"}

Returns: 0

We're best off not buying any shares, rather than buying and losing money.

2)

100

20

{"40 50 60", "37 48 55", "100 48 50", "105 48 47", "110 50 52", "110 50 52", "110 51 54", "109 49 53"}

Returns: 239

 

지난달 초까지는 어떤 주식도 팔 수 없다는 것을 기억하세요. 그러니, 거꾸로 일을 해보고,

우리의 돈을 투자하는 가장 좋은 방법이 무엇인지 알아봅시다.

 

두 번째부터 지난달(6월)까지의 주가는 모두 110, 51, 54로 우리가 팔던 가격보다 높기 때문에

그 달에는 아무것도 사지 않습니다.

다섯 번째 달 초에 세 번째 주식의 가격이 최종 가격보다 조금 낮기 때문에, 우리는 거기에 우리의 20을 투자하고, 겨우 20*((53/52)-1)을 벌었다. 4개월 초에 가격이 같아서 우리도 똑같이 해요.

3개월 초에는 가격이 바뀌었지만 여전히 3번째 종목에 투자하는 것이 최선이다. 세 번째 달 동안 세 번째 주식에 투자하여 얻는 이익은 돈을 저축하고 나중에 투자할 때보다 더 큽니다. 따라서, 우리는 3개월부터 20*((53/47)-1)의 이익을 우리의 20에서 얻습니다.

두 번째 달 초에는 우리 돈을 모두 저축한 다음, 가격이 더 낮은 다음 달 중에 세 번째 주식에 투자하는 것이 가장 좋습니다. 첫 번째 달 초에, 당신은 첫 번째 주식에 명확하게 투자해야 한다. 당신은 첫 주식의 가격이 조금 내려갈 때까지 당신의 모든 돈을 초기 투자로부터 저축해야 한다. 요약하면 다음과 같다:

month | action
------+-------
    0 | save
    1 | buy stock 0 (120/37 shares)
    2 | save
    3 | buy stock 2 (40/47 shares)
    4 | buy stock 2 (20/52 shares)
    5 | buy stock 2 (20/52 shares)
    6 | save
    7 | sell (3.243 shares of stock 0, 1.620 shares of stock 2)
Total sales price : 439.389
Total investment  : 200
Profit            : 239.389

---

Examples 설명에서 문제 풀이에 대한 대부분의 단서들을 주었다. 

 

문제의 핵심은 매달 주가의 가격을 보고, 투자를 하면 이를 마지막 달에만 판매할 수 있다는 것이고,

 

매달 monthlyContribution를 주어준다는 2가지 특징에 주목하면 문제를 쉽게 풀 수 있다.

 

첫 번째 달부터 마지막 달까지의 데이터가 미리 공개가 되어 있기 때문에

 

마지막 달에 판매를 했을 때 가장 높은 수익을 얻을 수 있는 달의 종목에 투자하면 된다. 

 

2월, 3월에 투자했을 때보다, 4월에 투자했을 때 더 높은 수익을 얻을 수 있으면 2월과 3월에는 

 

매수를 하지 않고  monthlyContribution을 저축하고, 4월에 사용하면 된다. 

 

Examples 설명에 문제의 Key가 되는 핵심 구절이 있다.

 

 

So, let's work backwards, and figure out what the best way to invest our money is.

 

우리는 주어진 주식 히스토리 데이터를 마지막부터 살펴보면서 가장 수익성이 높은 종목에 투자하면 된다. 

 

{"40 50 60",  ← (+270%) (-)           (-)

"37 48 55",   ← (+290%) (+2.0%) (-)

"100 48 50", ← (+9.0%) (+2.0%) (+6.0%)

"105 48 47", ← (+3.8%) (+2.0%) (+12.7%)

"110 50 52", ← (-)            (-)           (+1.9%)

"110 50 52", ← (-)            (-)           (+1.9%)

"110 51 54", ← (-)            (-)           (-)

"109 49 53"} ← 마지막 달의 종목 가격

 

위 케이스를 살펴보자. 

 

먼저 첫번째 달의 종목0을 매수하면 마지막 달에서 270%의 큰 수익을 올릴 수 있음에도 최대 리턴을 위해서는 

 

매수하면 안된다. 왜냐하면 다음 달에서 종목0에 투자하면 290%라는 더 큰 수익을 올릴 수 있기 때문에 

 

차라리 monthlyContribution을 저축하고 이 돈을 다음 달에 활용해야 한다. 

 

반대로 생각하면, 마지막 달부터 거슬러 올라가면서 종목마다 최대 수익률을 기록하고 이를 갱신하는 경우에만 

 

해당 종목을 매수하면 가장 최대 리턴을 얻을 수 있다.

 

이를 코드로 구현해보자. 

 

class StockHistory{
    public:
    int maximumEarnings(int initialInvestment, int monthlyContribution, vector <string> stockPrices){
        int money = initialInvestment;
        int month = stockPrices.size();
        int corp = 1;
        char *s = (char*)stockPrices[0].c_str();
        
        while(*s++){
            if(*s== ' '){
                corp++;
            }
        }

 초기 파라미터를 변수에 저장하고, 주식 데이터의 전체 월 개수, 종목 수를 구한다. 

        int prices[50][999];
        double max =0;

 문제의 파라미터로 주어지는 문자열 배열을 int 형으로 바꿔서 저장하기 위한 prices 배열과 

 

최고 수익률 판단의 지표인 max를 선언한다. 

        for(int i=0; i<month; i++){
            string s = stockPrices[i];
            for(int j=0; j<corp; j++){
                int pos = s.find(" ");
                // 공백을 찾는다.
                if(pos == string::npos){
                    prices[i][j] = atoi(s.c_str());
                    // 공백이 없으면 그 문자열을 통채로 int로 변환하여 저장.
                }
                else{
                    // 공백이 확인되면
                    prices[i][j] = atoi(s.substr(0, pos).c_str());
                    // 처음부터 공백이 확인된 위치만큼 문자열을 자르고 int로 저장.
                    s = s.substr(pos+1, s.size());
                    // 자른 문자열 이후로 다시 저장한다.
                }
            }
        }

 문자열 배열의 각 요소를 int 형으로 바꿔서 저장해주는 과정이다. 

        int buyThis[50] = {-1};
            //사고자 하는 종목이 몇번째 종목인지 저장.
        for(int i = month-2; i>=0; i--){
            for(int j=0; j<corp; j++){
                if(prices[i][j]-prices[month-1][j]>=0){
                    // 수익을 낼 수 없으면 건너뛴다.
                    continue;
                }
                double curReturn = 1.0*prices[month-1][j]/prices[i][j];
                // 수익률 계산
                if(curReturn >= max){
                    // max 값보다 크면
                    max = curReturn;
                    buyThis[i] = j;
                    // max를 갱신하고 어떤 종목인지 저장
                }
            }
        }

주식 가격 데이터를 마지막(에서 두번째)에서부터 훑으면서 가장 최고의 수익률(max)를 기준으로 

 

이 수익률보다 높으면 그 종목이 무엇인지 저장한다. 

 

        double totalProfit = 0;
        for(int i=0; i<=month-2; i++){
            if(buyThis[i] != -1){
                double profit = double(1.0*prices[month-1][buyThis[i]]/prices[i][buyThis[i]]-1);
                // 수익률 계산
                totalProfit += profit*money;
                // 수익률 누적
                money = 0;
            }
            money += monthlyContribution;
        }
        return (int)ceil(totalProfit);

이렇게 저장된 배열을 바탕으로 순회하면서 수익률을 누적하여 최종 결과를 반올림-int화하여 반환한다.