백준 c++ 1966 문제 풀이

문제 링크 : https://www.acmicpc.net/problem/1966

목차

1. 설명

 

2. 내 코드

 

3. 문제 풀이 해석 내용

 

4. 실행 결과

 

설명

백준 실버 3 문제 입니다.

문제명 : 프린터 큐

 

내 코드

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

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--)
    {
        int n, m;
        cin >> n >> m;

        queue<pair<int, int>> q;
        vector<int> v;

        for (int i = 0; i < n; ++i)
        {
            int p;
            cin >> p;
            q.push({ i,p });
            v.push_back(p);
        }

        sort(v.begin(), v.end(), greater<int>());

        int cnt = 0;
        int index = 0;

        while (!q.empty())
        {
            int curIndex = q.front().first;
            int curV = q.front().second;
            q.pop();

            if (curV == v[index])
            {
                cnt++;
                index++;

                if (curIndex == m)
                {
                    cout << cnt << '\n';
                    break;
                }
            }
            else
            {
                q.push({ curIndex, curV });
            }

        }
    }

}

 

문제 풀이 해석 내용

 

테스트 케이스 개수 입력

int t;
cin >> t;

int t;: 처리할 테스트 케이스의 총 개수를 저장하는 변수입니다.
cin >> t;: 사용자로부터 테스트 케이스의 개수 t를 입력받습니다.

 

 

각 테스트 케이스 내부 - 문서 정보 입력 및 초기화

    int n, m; // 문서 개수 n, 목표 문서 위치 m
    cin >> n >> m;

    queue<pair<int, int>> q; // {원래 인덱스, 중요도} 쌍을 저장하는 큐
    vector<int> v; // 중요도만 저장하는 벡터

    for (int i = 0; i < n; ++i)
    {
        int p; // 문서 중요도
        cin >> p;
        q.push({ i,p }); // 큐에 {i (0부터 n-1), 중요도 p} 저장
        v.push_back(p); // 벡터 v에 중요도 p 저장
    }

int n, m;: 문서의 총 개수 n과 목표 문서의 초기 위치(0부터 시작) m을 저장하는 변수입니다.
cin >> n >> m;: 사용자로부터 n과 m 값을 입력받습니다.

queue<pair<int, int>> q;: std::queue를 사용하여 문서들을 관리합니다. 

큐의 각 요소는 pair<int, int> 타입으로, {원래 인덱스, 중요도} 쌍을 저장합니다. 

원래 인덱스를 저장하는 것은 나중에 목표 문서(m)가 인쇄되었는지 확인하기 위함입니다.

vector<int> v;: std::vector를 사용하여 모든 문서의 중요도만 저장합니다. 

이 벡터는 중요도 순서대로 문서를 처리하는 데 사용됩니다.

for 루프를 사용하여 n번 반복하며 각 문서의 중요도 p를 입력받습니다.
q.push({ i,p });: 현재 문서의 {원래 인덱스 i, 중요도 p}를 큐 q에 추가합니다.
v.push_back(p);: 현재 문서의 중요도 p만 벡터 v에 추가합니다.

 

 

중요도 벡터 정렬

sort(v.begin(), v.end(), greater<int>());

sort(v.begin(), v.end(), greater<int>());: std::sort 함수를 사용하여 벡터 v에 저장된 모든 중요도를 내림차순으로 정렬합니다. 

가장 높은 중요도부터 차례대로 접근하기 위함입니다. 

greater<int>()는 내림차순 정렬을 위한 비교 함수 객체입니다.

 

 

출력 순서 계산

int cnt = 0; // 인쇄된 문서 개수 (출력 순서)
int index = 0; // 현재 인쇄될 중요도를 가리키는 v 벡터의 인덱스

while (!q.empty()) // 큐가 빌 때까지 반복
{
    int curIndex = q.front().first; // 큐의 앞 문서의 원래 인덱스
    int curV = q.front().second; // 큐의 앞 문서의 중요도
    q.pop(); // 큐에서 앞 문서 제거

    // 현재 문서의 중요도가 인쇄될 차례인 중요도(v[index])와 같으면
    if (curV == v[index])
    {
        cnt++; // 인쇄된 문서 개수 증가
        index++; // 다음 인쇄될 중요도로 이동 (v 벡터의 다음 요소)

        if (curIndex == m) // 현재 인쇄된 문서가 목표 문서(m)이면
        {
            cout << cnt << '\n'; // 현재까지 인쇄된 문서 개수(순서) 출력
            break; // 루프 종료 (문제 해결)
        }
    }
    else // 현재 문서의 중요도가 인쇄될 차례인 중요도보다 낮으면
    {
        q.push({ curIndex, curV }); // 문서를 큐의 뒤로 다시 보냄
    }
}

int cnt = 0;: 인쇄된 문서의 개수를 세는 변수입니다. 이 값이 목표 문서가 인쇄될 때의 순서가 됩니다.
int index = 0;: 정렬된 중요도 벡터 v에서 현재 인쇄될 차례인 중요도를 가리키는 인덱스입니다.
while (!q.empty()): 큐 q에 문서가 남아있는 동안 루프를 반복합니다.
q.front(): 큐의 가장 앞에 있는 문서의 {원래 인덱스, 중요도} 쌍을 가져옵니다.
q.pop(): 큐의 가장 앞에 있는 문서를 제거합니다.

 

if (curV == v[index]): 현재 큐에서 꺼낸 문서의 중요도(curV)가, 중요도가 가장 높은 문서부터 정렬된 v 벡터에서 현재 차례인 중요도(v[index])와 같으면, 이 문서를 인쇄할 수 있는 조건이 충족된 것입니다.
cnt++;: 인쇄된 문서 개수를 1 증가시킵니다.
index++;: 정렬된 중요도 리스트에서 다음으로 인쇄될 중요도를 가리키도록 index를 1 증가시킵니다.

if (curIndex == m): 만약 현재 인쇄된 문서의 원래 인덱스가 목표 문서의 인덱스 m과 같다면, 목표 문서가 인쇄된 것입니다.
cout << cnt << '\n';: 목표 문서가 인쇄된 순서(cnt)를 출력하고 줄바꿈합니다.
break;: 목표 문서를 찾았으므로 루프를 종료합니다.

else: 현재 큐에서 꺼낸 문서의 중요도가 v[index]보다 낮다면 (즉, 현재 문서보다 중요도가 높은 문서가 아직 큐에 남아있다면), 이 문서는 지금 인쇄될 수 없습니다.
q.push({ curIndex, curV });: 이 문서를 큐의 가장 뒤로 다시 보냅니다.

 

 

실행 결과