오답 노트 이분탐색을 할 때 주의할 것 백준 2805
정답률이 20% 초반인 문제 였고 그만큼 코너케이스가 많은 문제였다.
처음엔 딱 1번 틀렸고, 바로 수정해서 맞는 코드를 작성했으나...
Python으로 제출해서 시간초과가 났고
PyPy로 제출 할 때엔 sys.setrecursionlimit을 지우지 않아서 메모리 초과가 났다.
결국 맞는 코드를 PyPy로 제출하여 통과를 하게 되었지... 시간은 0.5초 가량이 소요 되었다.
여기서 알아 두어야 할 것.
PyPy가 실행속도가 Python 보다는 빠른 경우가 많다. (늘 빠른 것은 아니며, 인풋이 클 때에만)
다만 PyPy는 메모리를 Python보다는 많이 잡아먹는다.
특히 sys.setrecursionlimit은 메모리를
그런데 채점 현황을 보니 이상하다. 사람들이 Python 으로 제출해서도 2초~5초 가량이 걸리긴 했지만 잘 통과했기 때문이다. 그럼 내 코드는 5초도 더 걸렸다는 소리인데
분명히 내 코드에 비효율성이 있다는 뜻이니 꼼꼼히 살펴보기로 하자
좋은 것은 일단 통과한 코드가 있다는 것이다.
각종 반례를 내가 자유롭게 만들어서 기존 맞는 코드랑 비교하면, 틀렸는지 여부를 알 수가 있다.
일단 맞는 코드는 (PyPy로 제출해서 겨우 통과)
# 파이파이로 해서 겨우 통과
# 파이썬으로는 시간 초과
import sys
input = sys.stdin.readline
def biSearch(minlength, maxlength, target, trees): # min 이상 max 미만 기준 (반폐루프라, max는 포함 안함)
while True:
length = int((minlength + maxlength) / 2)
if (length == minlength):
return minlength
sawed = 0
for each in trees:
sawed += max(each - length, 0)
if sawed < target: # 더 낮게 잘라야 함 (그래야 조각이 더 나옴)
maxlength = length
elif sawed >= target: # 더 높게 잘라야 함 (그래야 조각이 덜 나옴)
minlength = length
if __name__ == "__main__":
N, M = map(int, input().split())
lst = list(map(int, input().split()))
print(biSearch(0, max(lst) + 1, M, lst))
여기서 주의 할 것은 아래처럼 작성하면 안된 다는 것이다.
아래 코드는 아예 틀린 코드다.
# 틀린코드 1 무한 루프 걸림
def biSearch(minlength, maxlength, target, trees): # min 이상 max 미만 기준 (반폐루프라, max는 포함 안함)
while True:
if (length == minlength):
return minlength
sawed = 0
for each in trees:
sawed += max(each - length, 0)
if sawed < target: # 더 낮게 잘라야 함 (그래야 조각이 더 나옴)
maxlength = length
elif sawed > target: # 더 높게 잘라야 함 (그래야 조각이 덜 나옴)
minlength = length + 1
else:
return lengthsawed = target으로 딱 목표 값으로만 자를 경우에만 리턴하도록 하면, 무한 루프에 걸릴 것이다.
자를 나무가 1개 이상이면, 딱 맞추어 자를 수 있겠지만. 자를 나무가 N개 이상이면, 1m씩 조정할 때마다 1m 이상 씩 증감할 것이니 말이다. (Nm씩 증감하는 것은 아니라는 것을 주의하자)
그래서 우리는 sawed >= target을 포함하여 다 살펴볼 것이다.
그래서 아래 처럼 짜보았는데, 무한 루프에는 걸리지 않았지만, 기존 정답 코드랑 몇몇 케이스에서 답이 어긋났다.
# 틀린 코드 2
def biSearch(minlength, maxlength, target, trees):
while True:
length = int((minlength + maxlength) / 2)
sawed = 0
for each in trees:
sawed += max(each - length, 0)
if sawed < target:
maxlength = length
elif sawed >= target:
if sawed - target < len(trees):
return length
minlength = length + 1디버깅을 해보았더니, sawed - target < len(trees) 라는 조건이 문제였다.
1m 씩 톱의 위치를 높인다고, 증가한다고 꼭 썰어지는 나무가 Nm 줄여지는것은 아니니까 말이다.
그런데 아래 처럼 하면 무한 루프에 걸린단 말이지...
sawed > target이 아니라 sawed>=target이라서 minlength = length+1로 할 수도 없는데....
# 틀린 코드 3 (무한루프)
def biSearch(minlength, maxlength, target, trees):
while (minlength < maxlength):
length = int((minlength + maxlength) / 2)
sawed = 0
for each in trees:
sawed += max(each - length, 0)
if sawed < target: # 더 낮게 잘라야 함 (그래야 조각이 더 나옴)
maxlength = length # 이상~미만이라서 결과적으로 length는 포함하지 않을 것임
elif sawed >= target: # 더 높게 잘라야 함 (그래야 조각이 덜 나옴)
minlength = length # 이상~미만이라서 결과적으로 length는 포함
return length
알고보니 minlength = length+1로 업데이트 후 while loop 종료 조건을 minlength < maxlength로 하면 되는 것이었다.
물론 그 전까지 값은 따로 저장해두어야 한다.
import sys
input = sys.stdin.readline
def biSearch(minlength, maxlength, target, trees): # min 이상 max 미만 기준 (반폐루프라, max는 포함 안함)
ret = 0
while (minlength < maxlength):
length = int((minlength + maxlength) / 2)
sawed = 0
for each in trees:
sawed += max(each - length, 0)
if sawed < target: # 더 낮게 잘라야 함 (그래야 조각이 더 나옴)
maxlength = length # 이상~미만이라서 결과적으로 length는 포함하지 않을 것임
elif sawed >= target: # 더 높게 잘라야 함 (그래야 조각이 덜 나옴)
ret = length if ret < length else ret
minlength = length + 1
return ret
N, M = map(int, input().split())
trees = list(map(int, input().split()))
print(biSearch(0, max(trees) + 1, M, trees))그런데 여전히 pypy로 하면 통과인데 ㅠㅠ python으로 하면 시간이 초과가 된다.
질문 게시판을 검색해보니, 부등호가 문제일 거라고 하는데 음...
알고보니 sawed가 문제였다. max()에서 시간이 많이 잡아먹었던것.... ㅠㅠㅠㅠ