본문 바로가기

Hanum.

1966 프린터 큐 본문

카테고리 없음

1966 프린터 큐

Han-um 2017. 1. 24. 03:05

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


 

◆ 문제 풀이


우선순위에 따라 규칙이 있는 큐를 구현하여, 원하는 문서가 언제 pop되는지 출력하는 문제입니다.

기본적으로 큐를 구현하되, 몇 가지를 추가로 고려하여야 합니다.

 

찾는 문서를 기록할 별도의 배열 혹은 2차원 배열이 필요

입력 1 1 9 1 1 1 예시를 보면 같은 숫자가 배열에 포함되어있으므로, 단순히 [1이 out되는 경우 출력하는것]으로는 문제를 해결할 수 없습니다.

따라서, 원하는 문서를 표시할 별도의 배열이 필요합니다.

 

기본적인 선형 탐색과 Que 알고리즘

가장 앞의 값과 뒤의 값들을 비교해, 더 큰 수가 있다면 앞의 값을 뒤로 밀어넣은 후, 제거합니다.

이 때, 위에서 언급한 추가 배열도 같은 과정을 진행해야 원하는 수가 out될때, 인식할 수 있습니다.

 

out과 카운트

더이상 뒷 배열에 더 큰 수가 없을 경우, 프린트한것으로 간주하고 앞에서 하나를 지웁니다.

이 때, 카운트를 누적시켜, 몇 번 프린트되었는지 체크하고, 만약 이번에 프린트된 것이 원하는 문서라면, 카운트를 저장합니다.

 

 


◆ 코드

 

#include <iostream>
#include <vector>
using namespace std;
//프린터큐
int main() {

 int num;
 cin >> num;
 int *counts = new int[num];

 for (int k = 0; k < num; k++) {

  int size, key, temp;
  cin >> size >> key; // 사이즈와 키를 입력받음
  vector<int> arr;
  vector<int> chk;

  for (int i = 0; i < size; i++) {
   cin >> temp;
   arr.push_back(temp);
   if (i == key) { // 원하는 숫자일 경우, 1을 넣어 마킹.
    chk.push_back(1);
   }
   else { // 원하는 숫자가 아닌 경우 0으로 초기화.
    chk.push_back(0);
   }
  }

 

  int mark = 0;
  int count = 0;
  while (mark == 0) {// 원하는 숫자가 출력될때까지 무한 반복한다.

   // 숫자가 하나일 경우 예외
   if (arr.size() == 1) {
    count++;
    break;
   }

   for (int i = 1; i < arr.size(); i++) { // 반복문이 끝난 후 : 한 번의 회전이 끝난다.
    if (arr.front() < arr.at(i)) { // 맨 앞의 값과 i번째 값을 비교, 더 큰 숫자가 있으면
     arr.push_back(arr.front());
     arr.erase(arr.begin());
     chk.push_back(chk.front()); // chk값도 마찬가지로 처리
     chk.erase(chk.begin());
     break;
     // arr[0]의 값을 뒤로 밀어넣는다. 반복문 탈출.
    }
    if (i == arr.size() - 1) { // 끝까지 와버렸어... 더이상 큰수가 없어...
     if (chk.front() == 1) {// 배열을 뺄 때, 해당하는 chk배열에 마킹이 되어있으면, 전체 탈출 후, mark값을 표기해 전체탈출
      count++;
      mark = 1;
      break;
     }
     else { // 아닐 경우(이번숫자이긴 한데 원하는숫자는 아니면) 숫자 빼고 카운트만 올려줌.
      arr.erase(arr.begin());
      chk.erase(chk.begin());
      count++;
     }
    }
   }
  }
  counts[k] = count;
 }

 for (int k = 0; k < num; k++) {
  cout << counts[k]<<"\n";
 }

 

 

 // arr와 chk 초기화해야함. 아니면 반복문에 넣던가.

 return 0;
}


by. 구 본철

Comments