문제 이해 단계
해당 문제는 간단해서 이해하는 데는 크게 어려움이 없었다.
그냥 자료구조 '큐' 안에 우선순위가 있는 문서들이 있는데,
우선순위에 따라 출력한다.그중 인덱스 M에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제.
첫 줄에는 이 테스트케이스를 실행할 횟수를 입력한다.
이후에는 문서의 개수 N, 타깃 문서의 인덱스 M,
다음 줄에는 각 자리에 있는 문서의 우선순위를 입력한다.
(숫자가 높을수록 우선순위가 높음)
문제 접근 단계
문제 자체는 명료해서 포인트를 우선순위가 중복될 수 있다는 점을 생각했다.
해당 테스트 케이스를 참고하여 문제를 구현하였다.
문제를 해결하기 위해 여러 가지 포인트들이 있었다.
포인트 1.
"내가 찾는 문서와 같은 우선순위 문서들을 어떻게 구분할까?"
내가 찾은 방법은 맨 처음 입력한 M을 인덱스 값처럼 사용해 그 위치를 계속해서 인지하는 것이었다.
그렇게 한다면 우선순위가 같은 문서들이 있어도 구분 가능할 것이라고 판단했다.
포인트 2.
"우선순위를 어떻게 인식해야 할까?"
요지는, 우선순위가 순차적으로 이어진 숫자가 아니라, 제멋대로라는 것이다.
예를 들어, 우선순위가 1,2,3이 아니라 1,2,9가 가능하다는 것이다.
만약 반복문을 통해 이를 전부 확인한다면 비효율적이고 시간초과가 뜰 수도 있다.
그래서 우선순위대로 정렬하고 이를 저장하는 리스트를 따로 둬, 하나씩 호출하였다.
전체적은 구현 함수는 다음과 같이 만들었다.
1.
문서들을 순서대로 큐에 저장하고, 입력받은 우선순위를 리스트에 저장해 이를 내림차순 정렬한다.
2.
큐 가장 앞에 있는 문서와 우선순위 리스트 중 가장 높은 우선순위를 비교한다.
우선순위가 일치하면 그 문서를 제거한다.
그렇지 않으면 해당 문서를 큐 가장 맨 뒤에 넣는다.
3.
이때 M(찾고자 하는 문서의 인덱스)를 큐 순서에 따라 갱신해 준다.
해당 과정을 M문서가 큐 가장 앞에 있을 때와 우선순위가 일치할 때까지 반복한다.
문제 구현 단계
vector<int> priorList; //우선순위를 저장할 큐
queue<int> queue; // 문서를 넣을 큐
for (int i = 0; i < amount; i++) {
int prior;
cin >> prior;
queue.push(prior);
priorList.push_back(prior);
}
//우선순위 판별을 위해 내림차순 정렬
sort(priorList.begin(), priorList.end(),greater<int>());해당 문제를 풀기 위해 STL 라이브러리를 추가해 문제를 풀어주었다.
문서의 개수(amount)만큼 우선순위가 적혀있는 문서를 큐에 넣고 동시에 우선순위 리스트에 넣는다.
이후 sort 함수를 이용해서 내림차순으로 정렬해 줬다.
int priorIndex = 0;
int ans = 1;
while (!queue.empty()) {
// 우선순위가 제일 높은 요소를 pop 가능할 때
if (queue.front() == priorList[priorIndex]) {
if (target == 0){ // 타겟가 가장 앞에 있을 때
return ans;
}else {
queue.pop(); //해당 문서 제거
priorIndex++; // 다음 높은 우선순위로 갱신
ans++; // 순서를 뜻하는 ans + 1
}
}
// 우선 순위가 제일 높은 요소가 아닐 때
else {
// 첫 요소를 마지막 요소로 넣음
int tmp = queue.front();
queue.pop();
queue.push(tmp);
}
if (target - 1 < 0) target = queue.size() - 1;
else target--;
}이후, 우선순위 값을 경신해 주기 위한 인덱스 priorIndex와 정답을 담을 ans=1로 초기화해 주는데,
이는 출력 순서가 1부터 시작하기 때문이다.
문제 구현 단계에서 언급했듯이, 큐 가장 앞에 있는 문서의 우선순위와
현재 가장 높은 우선순위가 일치하는지를 판단한다.
일치하면 그 문서가 타깃 문서인지 확인하고, 맞다면 return 틀리다면 해당 문서를 제거한다.
또한 타깃 문서가 맞다면, priorIndex와 출력 순서 ans를 갱신해 준다.
만약 해당 문서가 현재 우선순위가 가장 높은 문서가 아니라면, 이 문서를 다시 맨 뒤에 넣어준다.
위에 모든 비교가 끝나면 어떻게든 큐의 순서가 뒤바뀌어 있을 것이다.
따라서 target 문서의 큐 인덱스를 갱신해 준다.
이때 target 문서가 맨 뒤로 갈 가능성도 있기 때문에
인덱스가 0보다 작아지면 queue.size()-1을 통해 맨 마지막 인덱스로 보낸다.
아니면 target--를 통해 점점 앞으로 빼준다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int searchOrder(queue<int> queue,vector<int> priorList,int target) {
int priorIndex = 0;
int ans = 1;
while (!queue.empty()) {
// 우선순위가 제일 높은 요소를 pop 가능할 때
if (queue.front() == priorList[priorIndex]) {
if (target == 0){ // 타겟가 가장 앞에 있을 때
return ans;
}
else {
queue.pop();
priorIndex++;
ans++;
}
}
// 우선 순위가 제일 높은 요소가 아닐 때
else {
// 첫 요소를 마지막 요소로 넣음
int tmp = queue.front();
queue.pop();
queue.push(tmp);
}
if (target - 1 < 0) target = queue.size() - 1;
else target--;
}
return ans;
}
int main() {
int testCase; // 테스트 케이스 횟수
int amount; // 문서의 개수
int target; // 찾고자 하는 문서의 인덱스
cin >> testCase;
while (testCase-- > 0) {
cin >> amount >> target;
vector<int> priorList; //우선순위를 저장할 큐
queue<int> queue; // 문서를 넣을 큐
for (int i = 0; i < amount; i++) {
int prior;
cin >> prior;
queue.push(prior);
priorList.push_back(prior);
}
//우선순위 판별을 위해 내림차순 정렬
sort(priorList.begin(), priorList.end(),greater<int>());
cout << searchOrder(queue, priorList, target) << endl;
}
return 0;
}전체 코드는 다음과 같다.
여기서 sort 함수와 큐와 vector를 사용하기 위해,
#include <algorithm>과
#include <queue>, #include <vector>를 사용해 줬다.
시행착오
알고리즘 논리상으로는 전혀 무리가 없었고 괜찮았지만,
삼항연산자를 쓸 때 내가 잘못 사용하여 정답이 자꾸 다르게 도출됐다.
근데 그걸 모르고 함수 상의 오류인 줄 알고 2~3시간을 썼던 것 같다.
target = (target > 0) ? target-- : queue.size()-1;
// 해당 코드가 문제여서 이거를 아래 코드로 바꿨음
if (target - 1 < 0) target = queue.size() - 1;
else target--;위 코드에서 target = target--가 되는 것이 문제였다.
여기서 후위 연산자는 다음 코드에서 -1이 되기 때문에 target값이 그대로였던 것이 문제였다.
예를 들어 target = 5였다면 그대로 5가 target으로 들어갔던 것이다.
이 문제 이외에는 크게 문제 되는 것이 없었지만, 큐와 vector를 처음 사용해 봤기 때문에
STL 라이브러리 사용법을 익히는 데에 시간이 좀 걸렸던 것 같다.
해당 문제는 자료구조를 첫 사용으로는 괜찮았던 문제 같다.