백준[C언어] 1966: 프린터 큐

 

✅문제

1. 문서의 개수 N과 인쇄 순서를 알고 싶은 문서의 인덱스 M이 주어진다.

2. N개의 문서의 중요도가 0번~N-1번 인덱스 순서대로 주어진다.

3. 중요도가 높은 문서 먼저 인쇄된다. 

4. 중요도 최대값의 인덱스를 front로 둔다. 그리고 크기 N인 배열 하나 더 만들어서 이 front값을 해당 문서 인덱스 요소값으로 넣는다. 

5. front 기준 오른쪽으로 돌면서 그 다음 최대값을 찾아서 front+1로 둔다. 마찬가지로 해당 문서 인덱스 요소 값으로 front+1값을 저장.

6. 만약 배열의 끝(N-1)에 다다르면 0번 부터 front의 인덱스-1까지 5번과정 반복.

 

✅정리

step1) 크기가 N인 중요도 배열(요소값: 문서의 중요도) 과 큐 인덱스 배열(요소값: 큐 인덱스) 생성

step2) 중요도 배열에서 최대 중요도값을 찾고, 그것의 인덱스를 front라는 변수에 저장한다. 

step3) 큐 인덱스 배열에서 최대 중요도값의 인덱스 자리에 front값을 저장한다.  

step4) 중요도 배열에서 front인덱스 기준 오른쪽(front+1~)으로 돌면서 그 다음 최대값을 찾는다. 

이때 배열의 끝(N-1)에 다다르면 검색 중인 인덱스를 0으로 바꾸고 front-1까지 검색 계속한다.

step5) 최대값 찾을 때마다 count하고, count == N-1이 되면 검색 종료

step6) 완성된 큐 인덱스 배열을 가지고 원하는 문서인덱스[i]의 인쇄 순서를 구한다. 

 

👊Try 1

#include <stdio.h>
#include <stdlib.h>

int main()
{ 
  int i;
  int *Q_index; //큐 인덱스 배열
  int *Importance;  //중요도 배열
  int N, M; //N:문서 개수, M:원하는 문서인덱스
  scanf("%d %d", &N, &M);
  Importance = calloc(N, sizeof(int));
  Q_index = calloc(N, sizeof(int));
  for(i=0; i<N; i++)
  {
    scanf("%d", &Importance[i]);
  }

  //최대 중요도 값 검색
  int max_import = 0;
  int front;
  for(i=0; i<N; i++)
  {
    if(max_import <= Importance[i])
    {
      max_import = Importance[i];
      front = i;
    }
  }
  Q_index[front] = front;

  //front인덱스 기준 오른쪽으로 돌면서 그 다음 최대값 찾기
  max_import = 0;
  int temp;
  int count = 0;
  int search_index = front;
  do{
    for(i=++search_index; i<=search_index-1; i++)
  {
    if(search_index > N-1)
    {
      i = 0;
    }
    if(max_import <= Importance[i])
    {
      max_import = Importance[i];
      temp = i;
    }
  }
  //최대값 찾기 완료 하면
  count++;
  Q_index[temp] = front + count;
  Importance[temp] = 0;

  }while(count == N-1);
  
  int print_seq;
  print_seq = (Q_index[M] > front ? Q_index[M] : front) - (Q_index[M] < front ? Q_index[M] : front) +1; 
  printf("%d", print_seq);
  
  return 0;
}

❓문제 찾는 중