[BaekJoon 1966][⚪3] 프린터 큐
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (동적 배열)
- 알고리즘
Data Structure,queue
- 설명
vector를 사용하는 풀이이다.
queue로 프린터의 출력 순서를 관리함과 동시에 점수를 관리할 또 다른 컨테이너가 필요했는데, 이를 vector로 관리했다. 'vector'에 점수들을 요소로 삽입하고, 'sort'로 정렬한 뒤 'queue'의 맨 앞 요소와 'vector'의 맨 뒤 요소를 계속 비교하며 'pop', 'pop_back'을 반복하는 식으로 문제를 해결했다.
최악의 경우 출력해야 하는 요소가 queue에서 완전히 한 바퀴 돌고, 출력하면서 다시 한 바퀴 돌기 때문에 시간 복잡도는 O(N²)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
while(iT--)
{
int iN{}, iM{};
cin >> iN >> iM;
queue<pair<int, int>> qPrinter{};
vector<int> vecScore{};
vecScore.reserve(iN);
for(int i = 0; i < iN; ++i)
{
int iInput{};
cin >> iInput;
qPrinter.push({iInput, i});
vecScore.push_back(iInput);
}
// 점수 크기대로 정렬
sort(vecScore.begin(), vecScore.end());
int iCnt{ 1 }; // 몇 번째인지 카운팅 하는 변수
while(true)
{
pair<int, int> pairFront{ qPrinter.front() };
qPrinter.pop();
// 큐의 맨 앞 요소가 제일 큰 점수와 같을 때
if(pairFront.first == vecScore.back())
{
// 원하는 요소와 같은지 확인하고 출력
if(pairFront.second == iM)
{
cout << iCnt << '\n';
break;
}
++iCnt; // 카운팅 증가
vecScore.pop_back();
}
// 큐의 맨 앞 요소가 제일 큰 점수와 다를 때 다시 큐 맨 뒤로 이동
else
{
qPrinter.push(pairFront);
}
}
}
return 0;
}
2. 추가 풀이 1 (우선순위 큐)
- 알고리즘
Data Structure,queue
- 설명
priority_queue를 사용하는 방식이다.
위의 vector를 써서 정렬하고 맨 뒤의 요소와 비교하는 과정을 'priority_queue'의 자동 정렬과 'top', 'pop'으로 치환하는 방식이다. 개인적으로 이 문제의 가장 정석적인 풀이라고 생각한다.
위와 마찬가지로 시간 복잡도는 O(N²)이다
- 코드
내 풀이 코드
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
while(iT--)
{
int iN{}, iM{};
cin >> iN >> iM;
queue<pair<int, int>> qPrinter{};
priority_queue<int> pqScore{}; // priority_queue를 써서 삽입하면 내림차순으로 자동 정렬
for(int i = 0; i < iN; ++i)
{
int iInput{};
cin >> iInput;
qPrinter.push({iInput, i});
pqScore.push(iInput);
}
int iCnt{ 1 }; // 몇 번째인지 카운팅 하는 변수
while(true)
{
pair<int, int> pairFront{ qPrinter.front() };
qPrinter.pop();
// 큐의 맨 앞 요소가 제일 큰 점수와 같을 때
if(pairFront.first == pqScore.top())
{
// 원하는 요소와 같은지 확인하고 출력
if(pairFront.second == iM)
{
cout << iCnt << '\n';
break;
}
++iCnt; // 카운팅 증가
pqScore.pop();
}
// 큐의 맨 앞 요소가 제일 큰 점수와 다를 때 다시 큐 맨 뒤로 이동
else
{
qPrinter.push(pairFront);
}
}
}
return 0;
}
3. 추가 풀이 2 (배열)
- 알고리즘
Data Structure,queue
- 설명
배열만을 사용해서 해결하는 풀이이다.
위의 두 컨테이너를 사용하는 방식 대신, 배열만을 사용하는 방식이다. 방식은 위의 풀이들과 같지만, 배열을 통해 현재 최고 점수를 알아내는 반복문이 추가적으로 들어가야 한다.
가장 처음에 생각해낸 풀이였지만, 이 배열을 순회하는 추가적인 반복문이 거슬려서 첫 번째 풀이로 해결했다.
위와 마찬가지로 시간 복잡도는 O(N²)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
while(iT--)
{
int iN{}, iM{};
cin >> iN >> iM;
queue<pair<int, int>> qPrinter{};
int arrScore[10]{}; // 0 ~ 9 까지의 점수를 위한 공간을 미리 배열로 할당
for(int i = 0; i < iN; ++i)
{
int iInput{};
cin >> iInput;
qPrinter.push({iInput, i});
++arrScore[iInput]; // 맞는 배열의 인덱스의 숫자 증가
}
int iCurr{ 9 }; // 현재 가장 큰수를 가리키는 변수
// 가장 큰수가 뭔지 알아내는 반복문
while(iCurr >= 1 && arrScore[iCurr] == 0)
{
--iCurr;
}
int iCnt{ 1 }; // 몇 번째인지 카운팅 하는 변수
while(true)
{
pair<int, int> pairFront{ qPrinter.front() };
qPrinter.pop();
// 큐의 맨 앞 요소가 제일 큰 점수와 같을 때
if(pairFront.first == iCurr)
{
// 원하는 요소와 같은지 확인하고 출력
if(pairFront.second == iM)
{
cout << iCnt << '\n';
break;
}
++iCnt; // 카운팅 증가
--arrScore[iCurr]; // 해당하는 배열의 인덱스의 숫자 감소
while(iCurr >= 1 && arrScore[iCurr] == 0)
{
--iCurr;
}
}
// 큐의 맨 앞 요소가 제일 큰 점수와 다를 때 다시 큐 맨 뒤로 이동
else
{
qPrinter.push(pairFront);
}
}
}
return 0;
}
💭 후기
위의 세 풀이 모두 1 ≤ N ≤ 100이라는 크지 않은 범위 덕분에 O(N²)라는 시간 복잡도로도 0ms의 실행 시간이 나온다. 참고로 이러한 시간 복잡도가 나오는 과정에 대해 설명해보자면, 다음과 같은 조건이라고 해보자.
Index : 0 1 2 3 4 5
Priority : 1 2 3 4 5 6
- 내가 원하는 문서가
Index = 0의 문서라면 중요도가 가장 낮으므로 맨 마지막에 출력된다. - 중요도가 6인 문서부터 출력되어야 하므로
Index = 5인 문서까지 한 바퀴 도므로N번 반복한다. Index = 5부터 출력을 시작해서Index = 0인 문서까지 반복해야 하므로 다시N번 반복한다.
이런 식으로 시간 복잡도가 O(N²)이 나오는 것이다.
참고로 이렇게 시간 복잡도가 모두 같더라도 개인적으로 두 번째의 priority_queue를 사용하는 풀이가 가장 좋은 풀이라고 생각한다. '우선 순위'대로 '자동 정렬'한다는 컨테이너의 기능 자체가 이 문제와 딱 맞아 떨어지기 때문이다. 참고로 priority_queue의 삽입, 삭제의 시간 복잡도는 O(log N)이다.
Comments