youngmin.log

• [ 장르 ] STACK
• [ 문제 ]

[#42584] 주식가격

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

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int NoDownDuring;		// 해당시점 이후, 주식가격 낮아지기까지 시간체크
    
    answer.assign(prices.size(), 0);		// 주식 수 만큼 정답 벡터 0으로 초기화
    for(int i = 0 ; i < prices.size(); i++)
    {
        NoDownDuring = 0;		// 시간측정은 현 시점부터 0부터 시작
        for(int j = i + 1; j < prices.size(); j++)	
        {
            NoDownDuring++;
            if(prices[i] > prices[j])	// 현 시점 주식에서 뒤에 주식중에 현 시점 주식보다 낮은 시점
                break;
        }
        answer[i] = NoDownDuring;		// 현 시점에서 주식이 낮아지기까지 시간 벡터에 삽입
    }
    return answer;
}

• Another Code

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices)
{
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();

    for (int i = 0; i<size; i++)
    {
        // 스텍이 차있으면서 가격이 떨어지기 시작하면
        while (!s.empty() && prices[s.top()] > prices[i])
        {
            answer[s.top()] = i - s.top();
            s.pop();
        }

        // 가격이 올라갈때동안 스텍에 넣음
        s.push(i);
    }

    // 스텍에 남은것들을 계산해줌
    while (!s.empty())
    {
        answer[s.top()] = size - s.top() - 1;
        s.pop();
    }

    return answer;
}

[ CheckPoint ]

• 문제 의도만 파악하면, 문제는 어렵지 않은 문제다.
• 주된 장르는 스택인데, 나는 풀고나니 스택을 안았다. 스택을 써야하는 발상이 나지 않았다.
• 풀고나서보니, 최악의 상황 prices 벡터크기가 10000개이고, 모든 주식 가격이 같다면, 총 실행시간은 O(n^2)시간이 될 수 있다. 이는 굉장히 비효율적일 수 있는데, 이 문제는 이 사항은 수용하기로 했나보다.
• 다른 사람의 코드를 보면, 반복문이 2개가지만, 스택을 잘 활용해서 적어도 O(n^2)의 시간은 걸리지 않다는 것을 알 수있다.

• [ 장르 ] Stack / Queue
• [ Question ]

[#42586] 기능개발

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int CurFrontIndex = 0;	// 현재 제일 앞 우선순위 인덱스
    int releaseCount = 0;	// 현 시점 배포할 작업 수

    while(true)
    {
        while(progresses[CurFrontIndex] < 100)	// 현재 우선순위 인덱스 작업이 100% 될때까지
        {
            for(int i = CurFrontIndex ; i < progresses.size(); i++)	// 모든 작업, 스피드만큼 증가
                progresses[i] += speeds[i];
        }
        
        while(progresses[CurFrontIndex] >= 100 )	// 현재 우선순위 인덱스의 작업이 일단 100%끝난 시점에서 다음 작업으로 넘어가면서 다른 100%끝난 작업이 있는지 전진
        {
            releaseCount++;
            CurFrontIndex++;
            if(CurFrontIndex >= progresses.size())
                break;
        }
        if(releaseCount != 0)	// 한번 순회하면서 100% 완성된 작업 수 카운트를 정답 벡터에 push !
        {
            answer.push_back(releaseCount);
            releaseCount = 0;
        }
        if(CurFrontIndex >= progresses.size())	// 마지막 작업까지 끝나면 탈출
            break;
    }
    return answer;
}

• Better Code

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)		// 반복문 하나로 끝 
    {
        day = (99 - progresses[i]) / speeds[i] + 1;	// 매 작업마다 한 작업당 스피드로 나누면 몇일이 소요할 지 바로 나오겠지

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();		// 이 부분이 포인트라 했다. ++answer.back() ..

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

" 나는 정작 STACK을 잘 구현할려고 한 것인가 ? "

• [ CheckPoint ]

1.  이 문제의 작은 포인트는 작업이 100프로가 되면 작업을 중단하고 배포를 해야 한다는 것. 혹시 본인의 테스트 케이스가 대부분 맞는데 1,2개가 틀린다면 이 부분을 체크 해볼 것.
2. 나의 로직은 맨 앞 작업부터 끝나기까지 맨 끝 작업까지 한번 씩 speed만큼 작업의 진도를 증가 시키는 것인데, 만약 기존 작업량이 모두 낮고
   (10% 미만 ) speed는 각각 전부 1일 경우, 나의 알고리즘은 작업시간이 오래걸릴 것이다.
3. 좀 더 좋은 방법은 Better Code의  한 작업의 단계에서
   (99-현재작업의 량) / 작업의 speed + 1 = 남은 작업 일 수가 측정 됨을 생각하면 연산 한번의 이런 과정이 끝난다.
4. 아직 ++answer.push_back(1)의 의미를 정확히 모르겠는데 이해를 해봐야 겠다. 혹시 먼저 의견을 줄 수 있다면 조언을 주길 바란다.