[프로그래머스 / C++] 주식가격

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

문제 해결

i번째보다 작아지는게 언제인지 찾으면 되는 문제였다.

다만 time complexity가 O(n²)이 될것이기에 time complexity를 다른곳에서 최대한 아끼려고 했다.

- vector를 push_back 하지 않고 미리 memory를 할당하고 사용한 이유 : STL vector는 push_back시 memory 부족하다면 2배 정도씩 재 할당하게 된다. => 또, 기존 memory의 약2배 만큼의 메모리를 잡고 해당 memory로 카피하고 이전 memory를 해제 하기 때문에 memory를 미리 잡아두지 않으면 memory 할당,해제,복사 등으로 인해 시간 손해가 크다. (reserve도 좋다)

- 전위연산자(++count)를 사용한 이유: 전위연산자는 객체 자신을 증가시킨뒤 그 레퍼런스를 반환하고, 후위연산자는 객체를 복사한 임시 객체를 만들고 임시 객체에 연산한뒤 임시 객체를 반환한다. 그러므로 후위연산자(count++)는 copy construct에 의해 손해이므로 특별한 이유가 없다면 전위연산자를 쓰는게 좋겠다.

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    answer.resize(prices.size(), 0);

    for (size_t i = 0; i != prices.size() - 1; ++i)
    {
        size_t count = 0;
        for (size_t j = i + 1; j != prices.size(); ++j)
        {
            ++count;
            if (prices[i] > prices[j])
            {
                break;
            }
        }

        answer[i] = count;
    }

    return answer;
}

결과