https://www.acmicpc.net/problem/1966
문제 해결 과정
착안
얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue<> 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다.
본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 수 없다. 그런데 문제에서 우선순위가 높은 문서가 있는지 확인하는 것을 요구하므로 우선순위 값만 추가적으로 별도의 std::vector<> 클래스에 저장하고 정렬하여 출력 순서를 따지는 목적으로 활용하고자 하였다.
* 더 똑똑한 방법이 있을 수도 있겠지만, 편의상 이렇게 구현해보고자 하였음.
구현
Priorities 배열(std::vector<int>)을 오름차순으로 정렬하고, 하나씩 우선순위 값을 pop_back() 하여 큐에서 꺼낸 데이터의 우선순위가 해당 값과 같으면 출력 순서를 증가, 아니라면 큐에서 꺼낸 데이터를 다시 큐에 push() 하도록 구현하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Data
{
int Index;
int Priority;
};
int main()
{
int T, N, M;
cin >> T;
while (T--)
{
cin >> N >> M;
queue<Data> Queue;
vector<int> Priorities(N);
for (int i = 0; i < N; i++)
{
int priority;
cin >> priority;
Priorities.push_back(priority);
Queue.push(Data{ i, priority });
}
sort(Priorities.begin(), Priorities.end());
int order = 0;
while (!Queue.empty())
{
Data data = Queue.front();
Queue.pop();
int priority = Priorities.back();
if (data.Priority < priority)
Queue.push(data);
else
{
order++;
Priorities.pop_back();
if (data.Index == M)
{
cout << order << "\n";;
break;
}
}
}
}
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 10844번: 쉬운 계단 수 (0) | 2023.06.20 |
---|---|
[Baekjoon] 2559번: 수열 (0) | 2023.06.18 |
[Baekjoon] 9663번: N-Queen (0) | 2023.06.16 |
[Baekjoon] 1463번: 1로 만들기 (0) | 2023.06.15 |
[Baekjoon] 11866번: 요세푸스 문제 0 (0) | 2023.06.14 |
댓글