카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

https://school.programmers.co.kr/learn/courses/30/lessons/42587

풀이

중요도, 인덱스 정보를 한 쌍으로 가지는 큐

큐의 front 값이 최우선 순위인지 확인하기 위해 사용하는 우선순위큐

두가지를 사용해 풀이

우선 for문으로 큐(q)와 우선순위큐(pq)에 정보 push

우선순위큐의 top 에는 가장 값이 큰 데이터가 옴

따라서 현 시점에서 가장 높은 중요도를 찾을 수 있음

q의 front 값, 즉

q.front().first (중요도)

q.front().second (인덱스)

정보를 pq.front() 와 비교하여 q.front가 현 시점에서 가장 중요한 문서가 아니라면 해당 데이터를 다시 큐 뒤로 push

가장 중요한 문서라면 우선순위큐 pop 실행하여 다음 중요도 탐색 후 카운터 (cnt) 증가

여기서 만약 q.front().second (인덱스) 값이 내가 찾고자 했던 값, location의 값과 동일하다면 break로 while 반복문 탈출

    int solution(vector<int> priorities, int location) {
        int answer = 0;
        int cnt = 0;
        int size = priorities.size();
        queue<pair<int, int>> q;
        priority_queue<int> pq;

        
        for (int i = 0; i < priorities.size(); i++) {
            q.push(make_pair(priorities[i], i));
            pq.push(priorities[i]);
        }
        
        while(!q.empty()) {
            int val = q.front().first;
            int idx = q.front().second;
            q.pop();
            if (pq.top()==val) {
                pq.pop();
                cnt++;
                if (idx == location)
                    break;
            }
            else {
                q.push(make_pair(val, idx));
            }
        }
        answer = cnt;
        return answer;
    }

https://school.programmers.co.kr/learn/courses/30/lessons/42586

풀이

큐를 사용해도 되지만, 단순 for문으로 해결하기로 함

for문을 통해 progresses, speeds를 인덱스별로 순회하며 완료되는데 걸리는 시간 (duration)을 계산

처음엔 단순히 이전 duration과 현재 duration을 비교하여 현재 값이 작으면 앞의 값과 동시에 들어가도록 구현

그러나 duration이 5, 3, 4 일 경우 위와같이 구현하면 5, 3은 동시에 들어가고 4는 따로 들어가기 때문에 

answer = {2, 1} 이 나옴

하지만 실제로는 5일동안 모든 작업이 완료되기 때문에 answer = {3} 이 정답

** 해결

걸리는 최대 일수는 100일이기 때문에 max값 100으로 설정

max값과 duration을 비교하여 duration이 크다면, answer vector에 1 삽입

작다면 answer.back(), 즉 answer에 가장 최근에 들어간 값을 1 증가

이렇게 현재 duration 값보다 큰 값이 앞의 어느 부분에라도 있었다면 해당 값과 함께 삽입되도록 구현해야 정답

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

        int max = 0;
        for (int i = 0; i < progresses.size(); i++) {
            int duration = (100 - progresses[i]) / speeds[i];
            if ((100 - progresses[i]) % speeds[i] > 0)
                duration++;
            if (max < duration) {
                max = duration;
                answer.push_back(1);
            }
            else
                answer.back()++;
        }
        return answer;
    }