[백준: Python] 26086 - 어려운 스케줄링

[문제]

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

지문을 읽었을 때, 크게 어렵게 느껴지는 문제는 아니지만 최적화를 수행해야 한다는 점, 개인적으로 지문을 제대로 파악하지 못했던 점에서 다소 어려움이 있었던 문제입니다.

 

해당 문제의 관건은 요구사항대로 그대로 구현하되, 불필요한 연산을 수행하지 않음으로써 성능을 보장하는 것입니다.

---

[초기화]

    def __init__(self):
        self.n, self.q, self.k = map(int, input().split())
        self.cmd = [tuple(map(int, input().split())) for _ in range(self.q)]

---

[풀이]

    def solve(self):
        last_order = max([i if c[0] == 1 else 0 for i, c in enumerate(self.cmd)])  # 마지막 정렬이 일어난 위치
        flag = sum([c[0] == 2 for c in self.cmd[:last_order]]) % 2 != 0  # 마지막 정렬이 이뤄지기 전까지 뒤집기 여부
        dq = deque([c[1] for c in self.cmd[:last_order] if c[0] == 0])  # 맨 앞에 추가 = 가장 먼저 처리
        if last_order != 0:
            dq = deque(sorted(dq))  # 정렬 후, 고유번호 값이 낮은 업무가 스케줄러 앞에 배치 = 앞에 배치된 업무 먼처 처리
            flag = False  # 정렬 이후 업무 처리 기준이 새롭게 정의되었으므로 기존의 처리 순서 초기화

        for c in self.cmd[last_order:]:
            if c[0] == 0:
                dq.appendleft(c[1]) if not flag else dq.append((c[1]))
            elif c[0] == 2:
                flag = not flag

        print(dq[self.k-1] if not flag else dq[-self.k])

해당 문제는 명령어가 들어올 때마다 정렬을 수행하게 되면 O(QNlogN)의 시간복잡도를 가지게 되므로 시간초과가 발생합니다.

 

해당 문제의 관건은 정렬의 횟수를 최소화하는 것이 핵심입니다. 해당 문제에서 제시하는 정렬의 결과는 어떤 기준에 따라 달라지는 것이 아닌, 단순히 오름차순의 정렬입니다.

 

즉 [3, 1, 2]를 몇 번이고 정렬해도 결과는 [1, 2, 3]이 되는 것입니다. 이를 통해 정렬 명령어가 들어올 경우 마지막 명령만 수행하면 된다는 것을 알 수 있습니다.

 

풀이 순서는 다음과 같습니다.

1. 가장 마지막 정렬 명령어 탐색을 통해 해당 시점 저장
2. 정렬 전 마지막 뒤집기 연산의 상태 저장
   • 코드 상에서 flag로 나타낸 해당 부분은 사실 조건에 따라 True 혹은 False로 초기화하면 됩니다. 제가 가장 헤맸던 부분이 해당 부분인데, 저의 경우 정렬 전 가장 마지막 반전 연산 상태를 알아야 정렬 후 다음 값을 삽입할 위치를 정할 수 있다고 이해를 했지만 아닙니다. 문제에서는 다음과 같이 표현합니다.
     "이 결과, 고유번호 값이 낮은 업무일수록 스케줄러의 앞에 배치된다."
     기존에는 고유번호 상관없이 나중에 들어온 업무가 먼저 처리된다는 처리 순서가 있고 이는 반전 연산에 따라 달라지지만, 정렬이 되는 순간 업무 처리 순서의 기준이 새롭게 정의되므로 굳이 탐색을 통해 초기화할 필요가 없다는 것입니다.
3. 정렬 명령어가 있을 경우 정렬 수행
   • 위 설명에 따라 반전 연산 상태 초기화
4. 이후 삽입 연산과 반전 연산에 따라 값 처리
   • 편의를 위해 Deque 사용 → flag에 따라 값의 처리 방식이 스택과 큐의 형태를 띄기 때문
5. 마지막 반전 연산에 따라 값 출력
   • flag가 활성화(True)되어 있지 않다면 기존 연산 방향과 그대로 이므로 앞에서부터(스택) 값을 선택합니다. 반대로 활성화되어 있다면 뒤에서부터(큐) 값을 선택합니다.

아래는 2번의 부연설명에 맞춰진 코드입니다.

    def solve(self):
        last_order = max([i if c[0] == 1 else 0 for i, c in enumerate(self.cmd)])  # 마지막 정렬이 일어난 위치
        dq = deque([c[1] for c in self.cmd[:last_order] if c[0] == 0])  # 맨 앞에 추가 = 가장 먼저 처리
        if last_order != 0:
            dq = deque(sorted(dq))  # 정렬 후, 고유번호 값이 낮은 업무가 스케줄러 앞에 배치 = 앞에 배치된 업무 먼처 처리

        flag = False
        # 정렬이 일어났다면 반전 연산 초기화, 정렬이 일어나지 않았다면 실질적으로 8번 라인부터 코드가 실행되므로 이를 위한 상태 초기화
        for c in self.cmd[last_order:]:
            if c[0] == 0:
                dq.appendleft(c[1]) if not flag else dq.append((c[1]))
            elif c[0] == 2:
                flag = not flag

        print(dq[self.k-1] if not flag else dq[-self.k])

---

[전체 코드]

import sys
from collections import deque
input = lambda: sys.stdin.readline()


class Main:
    def __init__(self):
        self.n, self.q, self.k = map(int, input().split())
        self.cmd = [tuple(map(int, input().split())) for _ in range(self.q)]

    def solve(self):
        last_order = max([i if c[0] == 1 else 0 for i, c in enumerate(self.cmd)])  # 마지막 정렬이 일어난 위치
        flag = sum([c[0] == 2 for c in self.cmd[:last_order]]) % 2 != 0  # 마지막 정렬이 이뤄지기 전까지 뒤집기 여부
        dq = deque([c[1] for c in self.cmd[:last_order] if c[0] == 0])  # 맨 앞에 추가 = 가장 먼저 처리
        if last_order != 0:
            dq = deque(sorted(dq))  # 정렬 후, 고유번호 값이 낮은 업무가 스케줄러 앞에 배치 = 앞에 배치된 업무 먼처 처리
            flag = False  # 정렬 이후 업무 처리 기준이 새롭게 정의되었으므로 기존의 처리 순서 초기화

        for c in self.cmd[last_order:]:
            if c[0] == 0:
                dq.appendleft(c[1]) if not flag else dq.append((c[1]))
            elif c[0] == 2:
                flag = not flag

        print(dq[self.k-1] if not flag else dq[-self.k])


problem = Main()
problem.solve()

---