🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- 이분탐색, 재귀
- 절반씩 건너서 탐색 범위 줄이기
코드
- 일부 테스트만 통과, 정확성/효율성 실패
function solution(stones, k) { // 건너기 const step = (array, k, min, max) => { if (min === max) { return min; } const mid = Math.round((min + max) / 2); let count = 0; for (let i = 0; i < array.length; i++) { if (count === k) break; let stone = array[i] - (mid - 1); stone <= 0 ? count++ : 0; } if (count === k) { // 건널 수 없으면 범위 좁히기 return step(array, k, min, mid - 1); } else { // 건널 수 있으면 다음 범위 return step(array, k, mid, max); } } return step(stones, k, 1, 200000000); }
정은
구현
- 슬라이딩 윈도우 사용
코드
from collections import deque def solution(stones, k): max_arr = [] q = deque() q.append((-stones[0], 0)) max_arr.append(stones[0]) for i in range(1, len(stones)): tmp = stones[i] while q and -q[-1][0] < tmp: q.pop() q.append((-stones[i], i)) while i - q[0][1] >= k: q.popleft() max_arr.append(-q[0][0]) return min(max_arr[k-1:])
처음 코드(완전탐색) → 효율성 테스트 실패
def solution(stones, k): answer = 0 while True: currentIdx = -1 while currentIdx < len(stones): canWalk = False for step in range(1,k+1): currentIdx += step if currentIdx >= len(stones): canWalk = True break if (currentIdx < len(stones) and stones[currentIdx]): stones[currentIdx] -= 1 canWalk = True break if not canWalk: return answer answer += 1
종혁
구현
- 못 건너는 경우는 → 0이 연속으로 k번 이상 존재할때
- 1명부터(돌이 다 1일때) , 최대 2억명(돌이 다 2억일때)
- 안 될 때까지 한명씩 증가시켜서 찾는 방법보다, 이분탐색을 이용해야 될듯
- left - 1 , right - 2억으로 놓고 이분탐색
코드
function solution (stones, k) { let left = 1; let right = 200000000;//2억 while(left <= right) { const mid = Math.floor((left + right) / 2) //mid명이 건넜다고 가정 const copy = [...stones] let flag = false; let count = 0; for(let i = 0; i < copy.length; i++) copy[i] -= mid; for(const value of copy) { count = value <= 0 ? count+1 : 0; if(count === k) { flag = true; break; } } flag ? right = mid - 1 : left = mid + 1; } return left; }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- 숫자가 커지니까 확실히 테스트를 통과하기가 어렵다.
정은
종혁
재웅