🧩 문제 : 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문으로 작성해 시간을 줄여보려는 노력도 해보았다.
💭 결과
시간 초과와의 싸움이었다.
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 2022 사다리 (0) | 2023.02.09 |
---|---|
[BOJ / Python] 3107 IPv6 (0) | 2023.02.08 |
[프로그래머스 / Python] K번째 수 (0) | 2023.02.06 |
[프로그래머스 / Python] 체육복 (1) | 2023.02.05 |
[BOJ / Python] 1107 리모컨 (0) | 2023.02.04 |