[프로그래머스] 징검다리 건너기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 단순하게 이중반복문을 이용하여 모든 디딤돌을 탐색하는데, 하나의 디딤돌을 기준으로 k개만큼의 디딤돌을 확인하여 몇명이 지나가면 더 지나갈 수 없는지 확인하였습니다.

그러나 이중반복문이기에 시간초과가 발생하였습니다.

 

시간 초과를 해결하기 위하여 이분탐색을 이용하여 건너는 인원의 수를 구하는 방법으로 접근하였습니다.

2) 알고리즘

• 이분탐색

3) 풀이 코드

사용 언어 - Python

def solution(stones, k):
    low, high = 0, max(stones)          # 건널 수 있는 인원의 최솟값, 최댓값
    answer = 0                          # 건널 수 있는 인원

    while low <= high:                  # 이분 탐색
        can = (low+high) // 2           # 건널 수 있는 인원 설정
        cnt = 0                         # 돌다리 건널 수 없는 개수

        for idx in range(len(stones)):  # 돌다리를 탐색하여
            if stones[idx] < can:       # 현재 돌다리가 건널 수 없으면 
                cnt += 1                # 개수 증가
                if cnt >= k:            # k거리 만큼 벌어지면 종료
                    break
            else:                       # 건널 수 있으면 다시 0으로 할당
                cnt = 0
        
        if cnt >= k:                    # 현재 인원이 건널 수 없으면 인원을 더 줄여서 탐색
            high = can - 1
        else:                           # 현재 인원이 건널 수 있으면 인원을 더 늘려서 탐색
            low = can + 1
            answer = can                # 현재 인원은 건널 수 있으므로 정답에 저장
            
    return answer

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다