[プログラマー]橋を渡る
3500 ワード
渡る桥
コード#コード# def solution(stones, k):
lo = 1
hi = max(stones)
while lo < hi:
mid = (lo + hi) // 2 # mid = 징검다리를 건너는 친구 수
gap = 0 # 0의 개수
for i in range(len(stones)):
if stones[i] - mid <= 0: # 반복문으로 징검다리를 -1 하지 않고
# 친구수(mid)만큼 한번에 빼버린다.
gap += 1
else:
gap = 0 # 0이 연속적인 경우에만 고려해야하기 때문에 0으로 초기화
if gap >= k:
break
if gap >= k:
hi = mid
else:
lo = mid + 1 # lower bound
return lo
リファレンス
方法
この探索を通じて答えを探す.
ただし,答えがあらかじめ決まっているものと見なすべきである.
->すなわち、mid値を答えとして決定し、答え(mid)の順序を検証する
Reference
この問題について([プログラマー]橋を渡る), 我々は、より多くの情報をここで見つけました
https://velog.io/@guswns3371/프로그래머스-징검다리-건너기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
def solution(stones, k):
lo = 1
hi = max(stones)
while lo < hi:
mid = (lo + hi) // 2 # mid = 징검다리를 건너는 친구 수
gap = 0 # 0의 개수
for i in range(len(stones)):
if stones[i] - mid <= 0: # 반복문으로 징검다리를 -1 하지 않고
# 친구수(mid)만큼 한번에 빼버린다.
gap += 1
else:
gap = 0 # 0이 연속적인 경우에만 고려해야하기 때문에 0으로 초기화
if gap >= k:
break
if gap >= k:
hi = mid
else:
lo = mid + 1 # lower bound
return lo方法
この探索を通じて答えを探す.
ただし,答えがあらかじめ決まっているものと見なすべきである.
->すなわち、mid値を答えとして決定し、答え(mid)の順序を検証する
Reference
この問題について([プログラマー]橋を渡る), 我々は、より多くの情報をここで見つけました
https://velog.io/@guswns3371/프로그래머스-징검다리-건너기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について([プログラマー]橋を渡る), 我々は、より多くの情報をここで見つけました https://velog.io/@guswns3371/프로그래머스-징검다리-건너기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol