강의로 돌아가기
강수영

input이 요청시간 순서대로 들어오는 것이 아니라 랜덤인가요?

input이 요청시간 순서대로 들어온다고 생각을 했습니다.
그래서 vector에서 전부 priority_queue 에 넣고 시작하지 않고, start라는 변수를 둬서 해당 시간보다 작은 input들을 큐에 넣고
큐에 들어있는 값들 중 가장 짧은 작업을 수행하도록 구현하였습니다.
테스트케이스 2개정도를 추가해서 확인해도 맞았는데 채점해보니 15/100 더라구요 ...
(input이 요청순서대로 들어온다면) 로직에는 문제가 없다고 생각하는데 input이 랜덤으로 들어오는게 맞는지
제가 생각한 부분이나 구현이 이상한지 알고 싶습니다ㅠㅠ
처음에 다 큐에 넣는 방식으로 구현하니 풀리긴 합니다..

#include <string>
#include <vector>
#include<queue>

using namespace std;

struct comp{
    bool operator()(const pair<int, int> a, const pair<int, int> b){
        if(a.second == b.second)
            return a.first > b.first;

        return a.second > b.second; 
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int i=0;
    int start = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
    pair<int, int> tmp;    

    while(1){

        for(; i<jobs.size(); i++){
            if(jobs[i][0] <= start){ //작업이 진행된 시점까지 요청이 들어온 작업만 큐에 넣도록 하였습니다.
                pq.push(make_pair(jobs[i][0], jobs[i][1]));                
            }
            else{
                break;
            }
        }


        if(i == jobs.size()){
            break;
        }

       if(pq.empty()){
            start++;
            continue;
        }

        tmp = pq.top();
        pq.pop();
        answer += (start - tmp.first) + tmp.second;
        start += tmp.second;

    }

    while(!pq.empty()){
        tmp = pq.top();
        pq.pop();
        answer += (start - tmp.first) + tmp.second;
        start += tmp.second;
    }

    return answer/jobs.size();

}
  • SangJin Jeon
    랜덤이네요. 저도 처음 들어오는 배열을 큐에 먼저 넣어서 정렬 시키고, 그걸 순서대로 꺼내 쓰는 방식으로 해결했습니다. SangJin Jeon 2018.12.12 14:24
  • 김석일
    저도 랜덤인걸 모르고 풀어서 안풀렸는데 덕분페 풀었습니다. 감사합니다 ㅎㅎ 김석일 2019.01.23 14:48
1 개의 답변
Demi

input의 원소는 정렬되지 않은 채 들어옵니다. :)
즉, [[2,0], [0,3]] 같은 배열이 파라미터로 들어올 수 있습니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.