내 풀이

#include <iostream>
#include <queue>
using namespace std;

int n, m, k, l, _count = 0;

struct cmp 
{
    bool operator () (pair<int, int>& a, pair<int, int>& b)
    {
        if (a.first == b.first)
        {
            return a.second < b.second;
        }
        return a.first < b.first;
    }
};

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> m >> k;
        priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;

        for (int j = 0; j < m; ++j)
        {
            cin >> l;
            pq.push(pair<int, int>(l, j));
        }

        while (!pq.empty())
        {   
            if (k == pq.top().second)
            {
                cout << pq.top().second << endl;
                break;
            }
            else pq.pop();
        }
    }
    
    return 0;
}

pq에 밀어 넣을 때 cmp때문에 pair의 first값과 second값이 무조건 내림차순으로 정렬되면서 들어갈줄 알았는데 안들어가진다...

이유를 모르겠음..

밑에 코드는 안풀려서 다른 사람 코드 분석해서 작성한 부분

#include <iostream>
#include <queue>
using namespace std;

int n, m, k, l, _count = 0;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        _count = 0;
        cin >> m >> k;
        priority_queue<int> pq;
        queue<pair<int, int>> q;

        for (int j = 0; j < m; ++j)
        {
            cin >> l;
            q.push({j, l});
            pq.push(l);
        }

        while (!q.empty())
        {   
            int idx = q.front().first;
            int val = q.front().second;
            q.pop();
            if (pq.top() == val)
            {
                pq.pop();
                ++_count;
                if (idx == k)
                {
                    cout << _count << "\n";
                    break;
                }
                else q.push({idx, val});
            }
        }
    }
    
    return 0;
}

핵심은 while안에서 pq.top하고나서 _count++후에 idx값과 k의 값이 같은지보고 다르다면 뽑았던 부분 다시 q에다가 pair로 만들어서 넣어준다.

그러면 queue의 제일 위에 쌓이게 되고 하나하나씩 밑으로 나오게되면서 결국에는 k와 일치하는 idx값이 나오게 될 것이다.

궁금한점

그냥 pq에 넣을 때부터 모든것을 내림차순으로 넣으면 가능하지가 않나 생각이 드는데 cmp oeprator가 문제가 있는거는 아니겠고

내가 pq의 동작방식을 아직 정확하게 이해를 못한듯 하다.

cpp 코드

#include <iostream>
#include <queue>
using namespace std;
#define endl "\n"

int n, m, k, l;

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

	cin >> n;
	
	for (int i = 0; i < n; ++i)
	{
		cin >> m >> k;

		int cnt = 0;

		priority_queue<int> pq;
		queue<pair<int, int> > q;
		
		for (int j = 0; j < m; ++j)
		{
			cin >> l;
			pq.push(l);
			q.push( {j, l} );
		}

		while (!q.empty())
		{
			int idx = q.front().first;
			int val = q.front().second;
			q.pop();

			if (pq.top() == val)
			{
				pq.pop();
				++cnt;
				if (idx == k)
				{
					cout << cnt << endl;
					break;
				}
			}
			else q.push( { idx, val } );
		}
	}

	return 0;
}

while문 안에서 값이 pq와 q의 값이 같은 경우 pq에서 pop을 해주고 ++cnt를 늘려준다.

근데 만약 idx (중요도)가 같다면 원하던 값이니까 cnt를 출력을 해준다.