Informatica Online Judge

  스케쥴링 [0235 / 00EB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 48   Total Tried : 169


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 267byte
My Best Submission (C++) : N/A

[]

Background

스케줄링이란 특정 자원에 대해 그 자원을 요청하고 있는 대상들 중 누구에게 먼저 그 자원을 할당해 줄 것인가를 결정하는 일을 말하며, 그 중에서 특히 프로세스(Process) 스케줄링 기법은 프로세스들을 대상으로 프로세서(Processor) 자원을 할당해 주는 일을 말한다.

스케줄링 기법 중에 우선순위 알고리즘은 각 프로세스에 우선순위가 주어지고, 우선순위가 제일 높은 프로세스에 프로세서 자원이 할당된다.

우선순위가 같은 경우에는 은행의 번호대기표와 같이 FCFS(First-Come-First-Served)방식으로 처리된다.

우선순위 알고리즘에서 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스에 밀려 무기한 연기(indefinite postponement)가 발생될 수 있다.

이를 해결하기 위해 대기 시간이 경과할수록 대기하는 프로세스의 우선순위를 높여줌으로써 결국은 자원을 할당 받아 사용할 수 있도록 하는 에이징(aging) 기법 등이 사용된다.

본 문제는 우선순위 알고리즘과 에이징 기법을 응용하여 간단한 작업 스케줄링 프로그램을 작성하는 것이다.

입력데이터는 “프로세스 번호”, “그룹별 가중치”, “서비스 가중치”로 구성된다. 우선순위는 가중치의 합으로 결정되고, 가중치는 “그룹별 가중치”와 “서비스 가중치”의 합이다.

여기서 “그룹별 가중치”는 우선순위 알고리즘에서의 프로세스 우선순위이며, “서비스 가중치”는 에이징 기법에서 대기 시간이 경과할수록 대기하는 프로세스의 우선순위를 높여주기 위한 것이다. 다음의 조건, 입력 형식, 수행 과정, 출력 형식 등을 참조하여 작업 스케줄링 프로그램을 작성하시오.

[조건]

1) 우선순위는 가중치의 합으로 결정하고 가중치의 합은 “그룹별 가중치”와 “서비스 가중치”의 합으로 한다.

2) 가중치의 합이 높은 프로세스가 먼저 처리된다. (우선순위 알고리즘)

3) 가중치가 같을 경우에는 입력데이터의 순서에서 앞에 있는 프로세스가 먼저 처리된다. (First-Come-First-Served)

4) 입력데이터의 순서에서 뒤에 있는 프로세스가 먼저 처리된 경우에는 처리된 프로세스보다 앞에 있는 프로세스들의 “서비스 가중치”를 1씩 증가시 킨다. (에이징 기법)

5) 모든 입력데이터가 처리될 때까지 1)부터 4)의 조건을 반복하여 적용한다.

Input

1) 입력의 첫 번째 행은 처리할 데이터의 개수이다. 최대 100개 까지 처리할 수 있도록 작성한다.

2) 두 번째 행부터 처리할 데이터이다.

3) 처리할 데이터의 형식은 다음과 같다.



4) 그룹별 가중치의 값은 다음과 같다.



5) 가중치를 계산한 예는 다음과 같다.



수행과정]
가중치 계산의 예는 아래의 입력 예 데이터로 가중치의 합을 계산한 것이다. 프로세스 번호 104와 105가 가중치의 합이 5로 우선순위가 가장 높다(조건 2 우선순위 알고리즘). 둘 중 프로세스 번호 104가 먼저 입력되었으므로 먼저 처리된다(조건 3 FCFS). 그 후 프로세스 번호 101, 102, 103은 104보다 먼저 입력되었지만 104가 먼저 처리되었으므로 “서비스 가중치”가 1씩 증가된다(조건 4 에이징 기법). 다음의 그림은 프로세스 번호 104가 처리된 후 변경된 가중치의 합을 보여준다.



이때 프로세스 번호 101, 103, 105가 가중치의 합이 5로 우선순위가 가장 높다(조건 2 우선순위 알고리즘). 셋 중 프로세스 번호 101이 가장 먼저 입력되었으므로 먼저 처리된다(조건 3 FCFS). 프로세스 번호 101은 제일 먼저 입력된 것이므로 다른 프로세스들의 “서비스 가중치” 변화는 없다. 이후 모든 데이터들이 처리될 때까지 위의 과정을 반복적으로 수행한다.

Output

작업 스케줄링 프로그램에 의해 처리된 데이터는 출력에 각 행마다 처리된 순서대로 출력한다.(출력예 참조)

IO Example

입력
6
101C002
102D001
103A000
104B002
105C003
106D002


출력
104B002
101C003
103A001
105C003
102D004
106D002

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]