[프로그래머스 Lv2] : 프린터

문제 링크

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

코딩테스트 연습 - 프린터

우선순위가 정해져있는 문서들의 대기목록이 주어졌을 때 내가 원하는 문서가 몇 번째로 출력될지 리턴하는 문제.

풀이

• 풀이 알고리즘

주어진 priorities를 우선순위이자 인쇄 대기목록이라 했을 때, 대기목록 제일 앞. 즉, 0번째 인덱스에 있는 문서의 우선순위를 P라고 하자.

 1번째 문서부터 마지막 문서까지 중에서

1. P보다 우선순위가 높은 것이 없으면 0번째에 있는 문서를 인쇄한다.

2. P보다 우선순위가 높은 문서가 있다면 0번째에 있는 문서를 대기목록 제일 뒤로 보낸다.

일단 이게 기본적인 규칙이다.

 

 주어진 location은 출력 순서를 알고 싶은 문서의 인덱스이다. 0번째 문서를 인쇄하거나 맨 뒤로 보낼 때마다 location은 하나씩 줄어든다. 그러다가 location이 0이된 시점이 내가 원하는 문서를 출력할 차례가 된 것이다.

1. 내가 원하는 문서를 인쇄할 수 있다면. 즉, 대기목록에 우선순위가 더 높은 문서가 없다면 이때의 answer를 리턴한다.

2. 반대로 내가 원하는 문서를 출력할 수 없다면 이 문서를 대기목록 제일 뒤로 보내야하므로

location = 남아있는 문서의 수 - 1이 된다. 즉, priorites.size() - 1 이 된다.(인덱스는 0부터 시작하기 때문)

이 과정을 location이 0이 된 시점에 출력이 가능할 때까지 이 과정을 반복한다.

 

• 0번째 문서보다 우선 순위가 더 큰 문서가 존재하는지 파악하는 방법

나는 lower_bound 함수를 사용해서 이 문제를 해결했다.

lower_bound 함수는 범위 내에서 내가 정한 기준보다 크거나 같은 값이 처음으로 발견된 지점의 이터레이터를 반환한다. 만약 리턴값이 end()와 같다면 기준보다 크거나 같은 값이 벡터내에 존재하지 않는다는 뜻이다.

0번째 문서의 우선순위 + 1을 기준으로 lower_bound() 의 리턴값이 end()와 같다면 0번째 문서의 우선순위가 가장 높다는 뜻이다.

그리고 lower_bound 함수를 사용할 때에는 벡터가 정렬된 상태여야한다. 그런데 인쇄 대기목록을 정렬시킬 수는 없어서 temp라는 벡터에 값을 복사한 다음 temp를 정렬시켜줬다.

• 코드 작성

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> priorities, int location) {
    int answer = 0;
    while(true){
        vector<int> temp = priorities;
        sort(temp.begin(),temp.end());
        if(lower_bound(temp.begin(), temp.end(), priorities[0] + 1)
           == temp.end())
        {
            //뒤에 우선순위가 더 높은 문서가 없음
            //맨 앞의 문서 출력
            answer++;
            if(location == 0)
                break;
            priorities.erase(priorities.begin());
        }
        else{
            int temp = priorities[0];
            priorities.push_back(temp);
            priorities.erase(priorities.begin());
        }
        location--;
        if(location == -1)
            location = priorities.size()-1;
    }
    return answer;
}

 

정답 제출 후, 다른 사람들의 코드를 보면서 max_element라는 함수를 처음 알게됐다.

max_element는 범위 내에서 가장 큰 값의 이터레이터를 리턴해준다.

가장 큰 값을 얻고싶다면 이터레이터에 *을 붙여서 *max_element() 라고 하면된다.

0번째 문서의 우선순위가 대기목록 내에서 가장 크다면 0번째 문서를 인쇄한다.

priorities.begin() == max_element(priorities.begin(), priorities.end()) 라면 출력.