프린터

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

코딩테스트 연습 - 프린터

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>

using namespace std;

bool compare(std::pair<int, int> a, std::pair<int, int> b) {
    return a.second < b.second;
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    std::list<std::pair<int, int>> list;
    int pairIndex = 0;
    for (auto p : priorities) {
        list.push_back(std::make_pair(pairIndex++, p));
    }

    std::list<std::pair<int, int>> printList;

    while (true) {
        const auto front = list.front();
        list.pop_front();

        std::list<std::pair<int, int>> copyList;
        copyList.resize(list.size());
        std::copy(list.begin(), list.end(), copyList.begin());
        copyList.sort(compare);

        if (!copyList.empty() && (copyList.back().second > front.second)) {
            list.push_back(front);
        }
        else {
            printList.push_back(front);
            if (printList.size() == priorities.size()) {
                break;
            }
        }
    }

    int findIndex = 1;
    for (auto f : printList) {
        if (f.first == location) {
            answer = findIndex;
            return answer;
        }
        ++findIndex;
    }

    return answer;
}

 

 

느낀점

 효율적이고 짧은 코드를 생각 후 문제가 술술 풀리면 좋겠지만 직관적으로 풀이되는 방법을 통해 접근했다.

 문제풀이에는 제한된 시간이 있고, 좋은 방법을 고민하는것도 좋지만 반드시 풀리는 방법으로 접근 후 개선하는 것도 좋을것 같다는 생각.

 

문제 접근

  1. 링크드 리스트 사용, 대기목록에서 꺼낸 값을 뒷 값과 비교한다.

  2. 꺼낸 값을 제외한 값을 소팅한다.

  3. 소팅한 값의 가장 큰 값과 꺼낸 값을 비교한다.

  4. 비교해서 꺼낸 값(프린트 될 후보)이 가장 크다면 프린트 한다.  즉 순서가 결정됐다는 의미

  5. 그렇지 않은경우엔 가장 끝으로 보낸다.

 

c++ max_elements 라는걸 이용하면 코드가 많이 깔끔해질것 같다.

정답 후 다른사람 답안을 보니 max_element 를 사용해 간결하게 푼걸 볼 수 있었음

 

https://www.cplusplus.com/reference/algorithm/max_element/

max_element - C++ Reference