[백준/python3] 25603번 : 짱해커 이동식

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

25603번: 짱해커 이동식

---

알고리즘 분류

• 자료구조
• 우선순위 큐 
• 매개 변수 탐색
• 이분탐색

문제

짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다.

모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들을 받으려 한다. 하지만, 의뢰를 연속으로 K번 이상 거절하면 이동식의 실력이 거품이었다는 소문이 나기 때문에, 임의의 연속된 K개의 의뢰 중에서 최소 하나 이상의 의뢰는 받아야 한다.

이동식은 가능한 낮은 비용이 드는 의뢰만 받고 싶어 한다. 즉, 수락한 의뢰들의 비용 중 최댓값을 최소화하려 한다. 기업 의뢰 리스트가 주어졌을 때, 위 조건을 만족하면서 의뢰를 수행할 때 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라. 단, 주어진 의뢰의 순서를 임의로 바꿀 수 없다.

입력

첫 번째 줄에 정수 N, K가 주어진다. (1 =< K =< N =<100,000)
두 번째 줄부터 N개의 기업 의뢰의 비용이 주어진다. 비용은 1 이상 10^9 이하의 정수이다.

출력

이동식이 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라.

입출력 예제

---

풀이

가장 단순하면서 당연한 풀이로 접근할 수 있다. 구간 별 최소 값을 찾아, 그 중의 최대값을 찾는 것이다. 하지만 이 경우, 모든 경우를 다 확인해보기 때문에 매우 저열한 속도로 수행될 수 밖에 없다.

그러므로 최소값을 찾고, 이 최소값의 이후부터 다시 재탐색한다. 이를 통해 수행되는 연산 횟수를 줄일 수 있다.

---

코드

import heapq
N, K = map(int, input().split())
cost = list(map(int, input().split()))

# K==1 -> 가장 비용 높은 거로 하면 됨
if K == 1:
    print(max(cost))
#
else:
    ans_li = [] # 구간별 최솟값 저장
    min_idx = 0 # 슬라이딩 윈도우 시작 인덱스

    while min_idx + K <= N: # 슬라이딩 윈도우의 마지막 인덱스가 끝에 도달하지 않음
        slide = cost[min_idx:min_idx + K] # 현재 슬라이딩 윈도우
        min_val = min(slide) # 최소 비용 선택
        min_val_idx = slide.index(min_val) + min_idx # 최소값의 인덱스 찾기
        min_idx = min_val_idx + 1 # 그거 다음부터 확인 (그 앞은 다 min_val이 최소 비용이니까)
        heapq.heappush(ans_li, -min_val)

    print(-heapq.heappop(ans_li))

---