[C++] 큐(Queue), μš°μ„ μˆœμœ„ 큐(Priority Queue)

2020. 4. 30. 18:39Β·πŸ“ Computer Science/✏ Algorithm

큐(Queue)

큐

 

문제

 

https://www.acmicpc.net/problem/1966

 

1966번: ν”„λ¦°ν„° 큐

문제 μ—¬λŸ¬λΆ„λ„ μ•Œλ‹€μ‹œν”Ό μ—¬λŸ¬λΆ„μ˜ ν”„λ¦°ν„° κΈ°κΈ°λŠ” μ—¬λŸ¬λΆ„μ΄ μΈμ‡„ν•˜κ³ μž ν•˜λŠ” λ¬Έμ„œλ₯Ό 인쇄 λͺ…령을 받은 ‘μˆœμ„œλŒ€λ‘œ’, 즉 λ¨Όμ € μš”μ²­λœ 것을 λ¨Όμ € μΈμ‡„ν•œλ‹€. μ—¬λŸ¬ 개의 λ¬Έμ„œκ°€ μŒ“μΈλ‹€λ©΄ Queue 자료��

www.acmicpc.net

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

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

		queue<pair<int, bool>> q;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			if (i == m)
				q.push(make_pair(v[i], true));
			else
				q.push(make_pair(v[i], false));
		}

		sort(v.begin(), v.end());

		int result = 0;
		while (!q.empty()) {
			if (q.front().first == v.back()) {
				result++;
				v.pop_back();

				if (q.front().second) {
					cout << result << '\n';
					break;
				}
			}
			else 
				q.push(q.front());

			q.pop();
		}
	}
}

 

μš°μ„ μˆœμœ„ ν(Priority Queue)

top, popμ—μ„œ μΆ”μΆœλ˜λŠ” μ›μ†ŒλŠ” 제일 λ¨Όμ € λ“€μ–΄μ˜¨ 값이 μ•„λ‹Œ ν˜„μž¬ μš°μ„ μˆœμœ„ 큐 μ•ˆμ—μ„œ 제일 μš°μ„ μˆœμœ„κ°€ 높은 μ›μ†Œμ΄λ‹€.

보톡 νž™(Heap) 자료ꡬ쑰둜 κ΅¬ν˜„λœλ‹€.

 

문제

 

https://www.acmicpc.net/problem/11279

 

11279번: μ΅œλŒ€ νž™

첫째 쀄에 μ—°μ‚°μ˜ 개수 N(1≤N≤100,000)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” 연산에 λŒ€ν•œ 정보λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ xκ°€ μ£Όμ–΄μ§„λ‹€. λ§Œμ•½ xκ°€ μžμ—°μˆ˜λΌλ©΄ 배열에 xλΌλŠ” 값을 λ„£λŠ”(μΆ”κ°€ν•˜λŠ”) 연산이고, xκ°€ 0이라면 λ°°μ—΄μ—μ„œ κ°€μž₯ 큰 값을 좜λ ₯ν•˜κ³  κ·Έ 값을 λ°°μ—΄μ—μ„œ μ œκ±°ν•˜λŠ” κ²½μš°μ΄λ‹€. μž…λ ₯λ˜λŠ” μžμ—°μˆ˜λŠ” 2^31보닀 μž‘λ‹€.

www.acmicpc.net

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

int main(void)
{
	int n;
	cin >> n;

	// less<int>κ°€ μƒλž΅λœ μƒνƒœ
	// 큰 것뢀터 λ½‘λŠ”λ‹€.
	priority_queue<int> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

https://www.acmicpc.net/problem/1927

 

1927번: μ΅œμ†Œ νž™

첫째 쀄에 μ—°μ‚°μ˜ 개수 N(1≤N≤100,000)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” 연산에 λŒ€ν•œ 정보λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ xκ°€ μ£Όμ–΄μ§„λ‹€. λ§Œμ•½ xκ°€ μžμ—°μˆ˜λΌλ©΄ 배열에 xλΌλŠ” 값을 λ„£λŠ”(μΆ”κ°€ν•˜λŠ”) 연산이고, xκ°€ 0이라면 λ°°μ—΄μ—μ„œ κ°€μž₯ μž‘μ€ 값을 좜λ ₯ν•˜κ³  κ·Έ 값을 λ°°μ—΄μ—μ„œ μ œκ±°ν•˜λŠ” κ²½μš°μ΄λ‹€. μž…λ ₯λ˜λŠ” μžμ—°μˆ˜λŠ” 2^31보닀 μž‘λ‹€.

www.acmicpc.net

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

int main(void)
{
	int n;
	cin >> n;

	// μž‘μ€ 것뢀터 λ½‘λŠ”λ‹€.
	priority_queue<int, vector<int>, greater<int>> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

https://www.acmicpc.net/problem/11286

 

11286번: μ ˆλŒ“κ°’ νž™

첫째 쀄에 μ—°μ‚°μ˜ 개수 N(1≤N≤100,000)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” 연산에 λŒ€ν•œ 정보λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ xκ°€ μ£Όμ–΄μ§„λ‹€. λ§Œμ•½ xκ°€ 0이 μ•„λ‹ˆλΌλ©΄ λ°°μ—΄μ— xλΌλŠ” 값을 λ„£λŠ”(μΆ”κ°€ν•˜λŠ”) 연산이고, xκ°€ 0οΏ½

www.acmicpc.net

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

struct compare {
	bool operator()(int a, int b) {
		if (abs(a) == abs(b))
			return a > b;
		return abs(a) > abs(b);
	}
};

int main(void)
{
	int n;
	cin >> n;

	priority_queue<int, vector<int>, compare> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

https://www.acmicpc.net/problem/1715

 

1715번: μΉ΄λ“œ μ •λ ¬ν•˜κΈ°

μ •λ ¬λœ 두 묢음의 숫자 μΉ΄λ“œκ°€ μžˆλ‹€κ³  ν•˜μž. 각 묢음의 μΉ΄λ“œμ˜ 수λ₯Ό A, B라 ν•˜λ©΄ 보톡 두 λ¬ΆμŒμ„ ν•©μ³μ„œ ν•˜λ‚˜λ‘œ λ§Œλ“œλŠ” λ°μ—λŠ” A+B 번의 비ꡐλ₯Ό ν•΄μ•Ό ν•œλ‹€. 이λ₯Όν…Œλ©΄, 20μž₯의 숫자 μΉ΄λ“œ 묢음과 30μž₯οΏ½οΏ½

www.acmicpc.net

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

int num[10001];

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

	int N;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0, tmp; i < N; ++i) {
		cin >> tmp;
		pq.push(tmp);
	}

	int ans = 0;
	while (!pq.empty()) {
		int tmp = pq.top();
		pq.pop();

		if (!pq.empty()) {
			tmp += pq.top();
			pq.pop();

			ans += tmp;
			pq.push(tmp);
		}
	}
	cout << ans;
}

 

https://www.acmicpc.net/problem/1655

 

1655번: κ°€μš΄λ°λ₯Ό λ§ν•΄μš”

첫째 μ€„μ—λŠ” μˆ˜λΉˆμ΄κ°€ μ™ΈμΉ˜λŠ” μ •μˆ˜μ˜ 개수 N이 μ£Όμ–΄μ§„λ‹€. N은 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 100,000보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜μ΄λ‹€. κ·Έ λ‹€μŒ N쀄에 κ±Έμ³μ„œ μˆ˜λΉˆμ΄κ°€ μ™ΈμΉ˜λŠ” μ •μˆ˜κ°€ μ°¨λ‘€λŒ€λ‘œ μ£Όμ–΄μ§„λ‹€. μ •μˆ˜λŠ” -10,000보닀 ν¬κ±°λ‚˜ κ°™κ³ , 10,000보닀 μž‘κ±°λ‚˜ κ°™λ‹€.

www.acmicpc.net

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

int main()
{
	int n, m;
	cin >> n;

	priority_queue<int> low; // 쀑간값과 μž‘μ€ 수
	priority_queue<int, vector<int>, greater<int>> high; // 큰 수
	while (n--) {
		cin >> m;

		// κ·œμΉ™1. low.size() >= high.size()
		if (low.size() > high.size())
			high.push(m);
		else
			low.push(m);

		// κ·œμΉ™2. low.top() <= high.top()
		if (!high.empty() && !low.empty() && low.top() > high.top()) {
			int a = high.top(), b = low.top();
			high.pop(), low.pop();
			high.push(b), low.push(a);
		}
		cout << low.top() << '\n';
	}
}
μ €μž‘μžν‘œμ‹œ (μƒˆμ°½μ—΄λ¦Ό)
'πŸ“ Computer Science/✏ Algorithm' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [C++] 동적 κ³„νšλ²•(Dynamic Programming)
  • [C++] 덱(Deque)
  • [C++] μŠ€νƒ(Stack)
  • [C] 이진 탐색 트리(BST)
Blxxming
Blxxming
CS 지식과 κ³΅λΆ€ν•˜λ‹€ 배운 것, κ²½ν—˜ν•œ 것 등을 κΈ°λ‘ν•˜λŠ” λΈ”λ‘œκ·Έμž…λ‹ˆλ‹€.
  • Blxxming
    πŸ’‘λ²ˆλœ©πŸ’‘
    Blxxming
  • 전체
    였늘
    μ–΄μ œ
  • 곡지사항

    • Tech Interview
    • πŸ“š Tech (246)
      • πŸ“ Computer Science (96)
        • ✏ OS (12)
        • ✏ Network & Web (10)
        • ✏ Database (11)
        • ✏ Data Structure (6)
        • ✏ Algorithm (40)
        • ✏ Design Pattern (9)
        • ✏ Cloud Computing (3)
        • ✏ (5)
      • πŸ“ Language (73)
        • ✏ Language (6)
        • ✏ C & C++ (11)
        • ✏ C# (19)
        • ✏ JAVA (37)
      • πŸ“ Game (43)
        • ✏ Computer Graphics (2)
        • ✏ Unity (14)
        • ✏ Unreal (26)
        • ✏ (1)
      • πŸ“ Book (34)
        • ✏ Effective (3)
        • ✏ Game Server (16)
        • ✏ Clean Code (14)
        • ✏ (1)
  • hELLOΒ· Designed Byμ •μƒμš°.v4.10.0
Blxxming
[C++] 큐(Queue), μš°μ„ μˆœμœ„ 큐(Priority Queue)
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”