[BOJ / Python] 25603 짱해커 이동식

🧩 문제 : 25603 짱해커 이동식

 

👩🏻‍💻 문제 정리 

1. 짱해커 이동식은 비용이 적게 드는 의뢰를 받으려 한다. 

2. 그런데 K번 이상 거절은 불가능하다. -> 임의의 연속된 K개의 의뢰 중 하나는 꼭 받아야 한다. 

3. 이동식이 수락한 의뢰들이 가진 비용 중 가장 높은 비용을 구하면 된다. 

 

 

 

💪🏻 풀이 과정 

1️⃣  첫번째 - 시간 초과

import sys
input = sys.stdin.readline

N, K = map(int, input().split()) # N : 의뢰 개수, K : 연속으로 거절할 수 있는 최대 횟수
data = list(map(int, input().split())) # 의뢰 리스트

min_cost = 10**9
answer = 0
for i in range(N):
    answer = max(answer, min(data[i:i+K]))

print(answer)

 

2️⃣ N번째 - 성공

import sys
input = sys.stdin.readline

# -- 입력 --
# N : 의뢰 개수, K : 연속으로 거절할 수 있는 최대 횟수
# data : 의뢰 요청 리스트
N, K = map(int, input().split()) 
data = list(map(int, input().split())) 


start = 0 # start : 탐색을 시작할 인덱스 번호
answer = 0

# 의뢰 개수만큼 반복합니다. 
for _ in range(N): 
    end = 0
    min_cost = 10**9
    
    # K개의 의뢰 중에서 최소 하나 이상의 의뢰는 받아야 하므로 
    # start ~ start + K 만큼 반복문을 수행해 의뢰 비용이 적은 의뢰를 찾습니다. 
    for j in range(start, start + K):
    	# min_cost = min(data[j], min_cost)
        if data[j] < min_cost:
            min_cost = data[j]
            end = j # end : min_cost를 업데이트한 인덱스로 업데이트 

	# K개씩 탐색해 업데이트된 min_cost와 answer의 최댓값으로 answer를 업데이트합니다.
	# answer = max(answer, min_cost)
    if answer < min_cost: 
        answer = min_cost

    # end는 최솟값을 업데이트한 인덱스이므로 end + 1부터 end + 1 + K까지 탐색합니다. 
    # end + 1 + K 이 의뢰 개수를 초과한다면 data의 크기를 벗어나기 때문에 탐색이 종료됩니다. 
    # 탐색이 가능하다면 start를 end + 1로 업데이트한 후 또 다시 탐색합니다. 
    if end + 1 + K > N: break 
    else: start = end + 1 

print(answer)

 

📍 해결 방법

위 예시처럼 처음에 의뢰가 주어졌을 때 K개씩 모두 탐색을 했더니 시간초과가 나왔다. 그림을 그려보면서 초기 방식에 중복된 탐색이 존재함을 인식하게 되었고, 의뢰를 수락하면 그 다음 인덱스부터 탐색하도록 수정했더니 성공하였다.

또한 max()와 min() 함수가 O(n)의 시간복잡도를 가지고 있기 때문에 if문으로 작성해 시간을 줄여보려는 노력도 해보았다.

 

 

💭 결과

시간 초과와의 싸움이었다.