[BOJ/백준] 21777 리버스 가희와 프로세스

import sys

input = sys.stdin.readline
N = 1000001
max_priority = N//10
T = int(input())
INF = float('inf')
start_process_time = [INF]*N
end_process_time = [0]*N
arr = list(map(int,input().split()))
mono_times = 1
prev_process = -1
for i in range(T):
    cur_process = arr[i]
    if prev_process >= cur_process:
        mono_times += 1

    start_process_time[cur_process] = min(start_process_time[cur_process],mono_times)
    end_process_time[cur_process] = max(end_process_time[cur_process],mono_times)
    prev_process = cur_process


active_process_list = []
for i in range(N):
    if end_process_time[i]:
        active_process_list.append(i)



result = []
for process_id in active_process_list:
    priority = max_priority-1-start_process_time[process_id]
    spend_time = end_process_time[process_id]-start_process_time[process_id] + 1
    result.append((str(process_id),str(spend_time),str(priority)))


sys.stdout.write(str(len(active_process_list))+'\n')


for i in range(len(active_process_list)):
    sys.stdout.write(' '.join(result[i])+'\n')

 

이 문제 부터는 사실상 저 혼자만의 힘으로 푼 것이 아닌, 코딩개(chogahui05)님의 해설을 보고,

 

푼 것이기 때문에 온전한 실력이라고 할수 없고, 정확한 설명은 아래 링크를 참조하시길 바랍니다.

 

https://github.com/cdog-gh/gh_coding_test

cdog-gh/gh_coding_test

 

이 문제는 가희배 3번 문제 boj.kr/21773 의 연장선상이라고 보면 됩니다.

 

여기서는 실행된 프로세스 목록을 보고 프로세스의 우선순위와 실행시간을 구하는 문제입니다.

 

 

위의 설명에서도 잘 나와있듯이, 이 문제는 순증가수열별로 나누면 됩니다.

 

 

왜냐하면, 이 문제에서 먼저 같은 우선순위이면, 무조건 id가 적은것부터 나오게 됩니다.

 

그러므로 순증가수열 내에 있는 id들은 같은 우선순위로 시작하는 것을 알 수 있습니다.

 

그래서, 최초로 실행되는 위치이후로는 작업이 끝날때까지 매번 실행이 될것이기 때문에, 최초의 순증가 수열의 위치가

 

중요합니다.

 

그래서 여기서 구해야할것은 최초 프로세스가 실행되는 순증가수열의 최초의 위치,

 

그리고 프로세스가 마지막으로 실행되는 순증가수열의 마지막 위치, 이 두가지가 중요합니다.

 

만약 마지막 순증가수열의 프로세스 위치를 E 그리고 최초의 순증가 수열의 최초의 위치가 S라 하면

 

 

작업시간은 E - S + 1이 된다. 그리고 이 문제의 최대시간은 10^5이므로, 최대 priority 는 10^5+1로 설정을 하고, 

 

그 최대값에서 최대 priority - S를 해주면 된다.

 

 

 

# jthis님 풀이

import sys

input = sys.stdin.readline
N = int(input())
process_state = [[0 for _ in range(2)] for _ in range(1000001)]
# 0번 인덱스 총 시간
# 1번 인덱스 우선순위
arr = list(map(int,input().split()))

total_process = 0
for i in range(N):
    cur_process = arr[i]
    if not process_state[cur_process][0]:
        total_process += 1
    process_state[cur_process][0] += 1
 


pre_priority = 1
last_value = arr[-1]
process_state[last_value][1] = 1

for i in range(N-2,-1,-1):
    cur_process = arr[i]
    if not process_state[cur_process][1]:
        # 처음 나왔을때
        if cur_process<last_value:
            process_state[cur_process][1] = pre_priority
            # 이후의 값보다 낮은 값이면, 같은 순증가이므로, 같은 우선순위
        else:
            process_state[cur_process][1] = pre_priority + 1
    else:
        process_state[cur_process][1] += 1

    
    pre_priority = process_state[cur_process][1]
    last_value = cur_process


sys.stdout.write(str(total_process)+'\n')

for i in range(1000001):
    if process_state[i][0]:
        sys.stdout.write(str(i)+' '+str(process_state[i][0])+' '+str(process_state[i][1])+'\n')

 이 방식은 앞선 방식과 뒤에서부터 찾아가는 방식이다. 

 

먼저 전체 실행시간은 반복문을 돌리면서 총 시간을 더해준다.

 

그리고 이 문제에서 쓰는 프로세스의 종류는 total_process를 통해 구해준다.

 

이 문제도 같은 순증가 수열에 있는건지 확인을 해주는 방식이다.

 

이 문제의 우선순위가 낮은것부터 제일 뒤에서부터 실행되는 것을 응용한 것이다.

 

 

가장 마지막에 실행되는 것은 일단 가장 우선순위가 낮은 1일 것이다.

 

그리고 그때의 process_id보다 그이전의 process_id가 낮다는 것은 같은 순증가수열에 있고,

 

같은 우선순위 그룹에 잇는 것임을 알 수 있다. 그러므로 최초의 우선순위를 같게 설정을 해주면 된다.

 

그런데 만약 이전 process_id가 더 크거나 같으면, 다른 순증가 수열에 있는 것이므로,

 

현재 우선순위보다 1을 높여줘야한다.

 

그리고 최초로 만난 프로세스가 아니라면, 이미 자기의 초기 우선순위를 알고 있으므로, 1씩 증가시켜 주면 된다.

 

이 문제는 프로세스의 수행시간이 어떻게 되는지, 우선순위가 어떻게 구성되는지에 대해서

 

알아야 풀 수 있는 문제인것같다.