[프로그래머스] 프린터 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 프린터 문제입니다.

 

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

 

 

 

 

 

 

 

해결 과정

 

 

문제 특성 상 앞에 있는 원소를 뒤로 보낸다거나 앞에 있는 원소를 제거하는 작업이 많아. deque를 채택하였습니다.

문제에선 가장 중요도가 높은 작업물의 출력을 우선 시 하기에 priority queue를 사용할까 하였지만 그렇게 되면

우리가 찾는 원소가 중복의 경우에는 구분할 수가 없어 포기하였습니다.  

전체적인 흐름은 deque가 빌 때 까지 반복하며 반복중에 우리가 찾는 원소가 나가면 반환과 종료합니다.

deque의 가장 큰 원소를 찾기 전까지 가장 큰 앞의 원소들을 전부 deque의 뒤로 보냈습니다.

그리고 가장 큰 원소를 출력하게 되면서 출력물의 갯수를 더하고 값을  deque에서 제거를 합니다. 

이러한 반복되는 과정에서 저희가 찾고자 하는 원소를 구분하기 위해 입력의 location값을 반복문에서 추적합니다. 

이후 반복과정을 마치고 답을 반환합니다.

 

 

 

 

 

코드 전문

 

 

#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solution(vector<int> p, int location) {
    int answer = 0;
    deque<int> q;
    for (auto i : p)
        q.push_back(i);
    while (!q.empty())
    {
        for (auto i = q.begin(); i < max_element(q.begin(),q.end()); i++)
        {
            cout << q.front();
            q.push_back(q.front());
            q.pop_front();
            if (location == 0) location = q.size()-1;
            else location--;
        }
        
        answer++;
        if (location == 0) break;
        q.pop_front();
        if (location == 0) location = q.size()-1;
        else location--;
    }
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

처음에 이중반복문으로 구현을 하니 시간초과로 예상치 못한 일들이 일어났습니다. 이후 문제의 특성을 이용해

deque를 채택하고 stl의 최적화된 함수들을 사용하니 풀 수 있었습니다. 

내부의 location을 통한 추적이 두 부분에 쓰이며 가독성을 해치진 않을까 생각이 들었습니다.

주의하겠습니다.

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.