정답 비율 25.559%...
처음에는 단순히 탐색하는 방식에서 탐색 범위를 줄이고 이중반복문을 사용하지 않음으로써 시간을 줄여보고자 했다.
(a = 나무 리스트)
1. max(a) - m보다 큰 값만 존재하는 b리스트를 하나 더 생성 (조건을 만족하지 않는 나무들은 개수에 영향을 주지 않으므로)
2. max(a) - m ~ max(a)+1의 범위만 탐색하며 조건에 맞으면 출력, break
결과는 시간초과가 났다,,
시간초과 코드
import sys
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = []
for i in range(len(a)):
if a[i] > (max(a)-m):
b.append(a[i])
for i in range(max(a)-m,max(a)+1):
c = sum(b) - i * len(b)
if c == m:
print(i)
break
elif c < m:
print(i-1)
break
8번 줄의 새로운 배열에 append하는 과정이 시간을 많이 잡아먹은 것 같다.
(테스트 케이스에서는 답이 잘 나왔지만) 백준에서는 시간 초과라고만 나와서 답이 정확히 맞은건지도 모르겠다.
배열을 전수조사하지 않고 절반씩 범위를 줄여가는 방식의 이분 탐색을 사용하여 해결하였다.
이분 탐색은 O(logN)의 시간복잡도를 가진다.
정답 코드
import sys
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
left = 0
right = max(a)
result = 0
while left <= right:
count = 0
mid = (left + right) // 2
for tree in a:
if tree > mid: #해당 나무가 절단기 높이보다 높은 경우에만
count += (tree - mid) #해당 나무에서 절단기 높이를 뺀 만큼을 더해줌(잘린 나무의 높이)
if count >= m: #추가하는 중에 이미 구할 나무(m)을 초과해버린 경우 break
break
if count >= m: #자를 양보다 많이 자르거나 딱 맞추어 자른 경우
result = mid #result값에 현재 절단기 높이(mid) 할당
left = mid + 1 #우측으로 범위 축소(절단기를 높여야 함)
else: #자를 양보다 적게 자른 경우 (문제 조건 위배)
right = mid - 1 #좌측으로 범위 축소(절단기를 낮춰야 함)
print(result)
코드 설명은 주석을 보면 될 것 같다.
헷갈린 부분
for tree in a:
if tree > mid:
count += (tree - mid)
if count >= m: #추가하는 중에 이미 구할 나무(m)을 초과해버린 경우 break
break
4, 5번째 줄의 코드를 추가하기 전에 시간초과가 났다.
나무를 추가하는 도중 count가 m을 도달한 경우, for문을 빠져나오게 한다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준 알고리즘] 2231번: 분해합 (파이썬 / Python) (1) | 2022.08.03 |
---|---|
[백준 알고리즘] 10814번: 나이순 정렬 (파이썬 / Python) (0) | 2022.08.02 |
[백준 알고리즘] 17478번: 재귀함수가 뭔가요? (파이썬 / Python) (0) | 2022.08.02 |
[백준 알고리즘] 10870번: 피보나치 수 5 (파이썬 / Python) (0) | 2022.08.02 |
[백준 알고리즘] 2839번 : 설탕 배달 (파이썬 / Python) (0) | 2022.08.01 |