📝18258번: 큐 2
문제 설명
큐 2
해결 방법
C++ STL에서 제공하는 queue를 사용한다.
push는 큐에 원소를 삽입하는 연산
size는 큐의 크기를 구하는 연산
front는 큐에서 가장 첫번째로 들어온 원소를 반환하는 연산
back은 큐에서 가장 마지막에 들어온 원소를 반환하는 연산
pop은 front에 있는 원소를 제거하고 반환하는 연산
empty는 큐가 비어있는지 확인하는 연산으로 비어있다면 1, 비어 있지 않다면 0을 반환한다.
주의할 점은 pop, front, back 연산 시 스택이 비어있다면 -1을 출력해야 한다.
💻소스코드
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
queue<int> q;
string str;
for (int i = 0; i < N; i++) {
cin >> str;
if (str == "push") {
int num;
cin >> num;
q.push(num);
}
else if (str == "size") {
cout << q.size() << "\n";
}
else if (str == "front") {
if (!q.empty())
cout << q.front() << "\n";
else
cout << "-1\n";
}
else if (str == "back") {
if (!q.empty())
cout << q.back() << "\n";
else
cout << "-1\n";
}
else if (str == "pop") {
if (!q.empty()) {
cout << q.front() << "\n";
q.pop();
}
else
cout <<"-1\n";
}
else if (str == "empty") {
if (!q.empty())
cout << "0\n";
else
cout << "1\n";
}
}
return 0;
}📝2164번: 카드2
문제 설명
카드2
해결 방법
카드를 1부터 입력 N까지 순서대로 큐에 넣는다. 그럼 front는 1이 되고 back은 N이 된다.
큐에서 front를 pop 한다. 그 다음, 큐의 front를 다시 큐에 push 하고 front를 pop 한다.
마지막에 남은 카드를 출력해야 하므로 큐에 원소가 한 개 남을 때까지 반복한다.
💻소스코드
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
// 카드 2
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
queue<int> q;
cin >> N;
for (int i = 1; i <= N; i++) { // 카드를 1부터 N까지 순서대로 큐에 넣는다.
q.push(i);
}
// 카드가 한 개 남을때 까지 반복
while (q.back() != q.front()) {
q.pop(); // 제일 위에 있는 카드를 버린다.
q.push(q.front()); // 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
q.pop();
}
cout << q.front() << "\n";
return 0;
}📝11866번: 요세푸스 문제 0
문제 설명
요세푸스 문제 0
해결 방법
큐에 1부터 N까지 숫자를 차례대로 삽입한다.
K번째 사람을 제거하기 위해 cnt를 1부터 늘려가면서 K로 나눴을 때 나머지가 0일 때 원소 출력하고 제거한다.
큐가 비어있을 때>를 출력하고 비어있지 않다면,,를 출력한다.
cnt를 K로 나눴을 때 나머지가 0이 아니라면, 당장 제거 대상이 아니므로 pop 하고 push 해서 순서를 뒤로 미룬다.
💻소스코드
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// 요세푸스 문제 0
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
queue<int> q;
// 큐에 숫자를 삽입
for (int i = 1; i <= N; i++) {
q.push(i);
}
// 순서대로 K번째 사람을 제거
int cnt = 1;
cout << "<";
while (!q.empty()) {
if (cnt % K == 0) {
cout << q.front();
q.pop();
if (!q.empty())
cout << ", ";
else
cout << ">";
}
else {
q.push(q.front());
q.pop();
}
cnt++;
}
return 0;
}📝1966번: 프린터 큐
문제 설명
프린터 큐
해결 방법
문서의 '중요도'를 포함하는 priority_queue, 문서의 입력 '순서'와 '중요도'를 포함하는 pair를 활용한 queue, 인쇄 순서를 카운트할 변수 cnt를 선언한다.
입력 순서를 first, 중요도를 second로 queue에 push하고, 중요도를 priority_queue에 push한다.
(우선순위 큐의 경우 자동으로 중요도가 큰 순서대로 top에 위치한다.)
큐 front의 중요도가 낮으면 큐의 뒤로 보낸다. (pop 순서를 맨 뒤로 미룸)
큐 front의 중요도와 우선순위 큐의 top이 일치하면 인쇄한다.
💻소스코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
// 프린터 큐
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// T: 테스트 케이스 수, N: 문서의 개수, M: 현재 queue에서 몇 번째 놓여 있는지, imp: 중요도
int T, N, M, imp;
cin >> T;
for (int i = 0; i < T; i++) {
int cnt = 0;
priority_queue<int> pq; // 문서 중요도
queue<pair<int, int>> q; // 문서 정보
cin >> N >> M;
for (int j = 0; j < N; j++) {
cin >> imp;
q.push({j, imp});
// q.emplace(j, imp);
pq.push(imp);
}
while (!q.empty()) {
int idx = q.front().first; // 문서 순서
int importance = q.front().second; // 문서 중요도
// 중요도가 밀리면 q에서 뒤로 보냄
if (pq.top() > importance) {
q.push(q.front());
q.pop();
}
else { // 인쇄
pq.pop();
q.pop();
cnt++;
if (idx == M) {
cout << cnt << "\n";
break;
}
}
}
}
return 0;
}