징검다리 건너기

문제 보기 · Level 3 · 2019 카카오 개발자 겨울 인턴십 · 정답률 51% · 푼 사람 10,875명 (2026-09-30 기준)¹

문제

디딤돌이 한 줄로 놓여 있고 돌마다 숫자가 적혀 있다. 한 번 밟을 때마다 숫자가 1씩 줄고, 0이 된 돌은 밟을 수 없다. 친구들은 한 명씩 왼쪽 강가에서 오른쪽 강가로 건넌다. 다음에 밟을 수 있는 돌이 여러 개면 가장 가까운 돌만 밟는다. 한 번에 건너뛸 수 있는 거리는 최대 k칸이다. 최대 몇 명이 건널 수 있는지 돌려준다.

돌 1~200,000개, 숫자 1~200,000,000
1 ≤ k ≤ 돌 개수

풀이

막히면 한 단계씩 펼친다.

필요한 개념

매개변수 탐색: “최대 몇 명?”을 “m명째도 건널 수 있나?”로 바꾸고, m을 이분 탐색한다.
연속과 사잇값 정리: 방정식의 근을 찾는 이분법과 같은 틀이다. 양 끝의 결과가 다르면 가운데를 보고 절반을 버리며 경계를 좁힌다. 이분법은 연속에 기대어 근이 있음을 알고, 여기서는 판정이 참에서 거짓으로 한 번만 바뀐다는 성질에 기댄다.

1단계 · 작은 예로 손으로 풀기

돌 [2, 1, 3], k = 2

1번째 친구: 세 돌을 모두 밟는다. 돌은 [1, 0, 2]가 된다.
2번째 친구: 가운데 돌이 0이라 첫 돌에서 셋째 돌로 2칸 뛴다. 된다. 돌은 [0, 0, 1].
3번째 친구: 강가에서 셋째 돌까지 3칸이라 k = 2를 넘는다. 못 건넌다.

답은 2다. 규칙이 보인다. 친구는 밟을 수 있는 돌을 모두 밟는다(늘 가장 가까운 돌로 가니까). 그래서 m − 1명이 지나간 뒤 돌의 숫자는 “처음 숫자 − (m − 1)”이고, 처음 숫자가 m보다 작은 돌은 0 이하가 되어 밟을 수 없다.

2단계 · 가장 단순한 방법과 그 속도

친구를 한 명씩 실제로 건너게 한다. 한 명에 \(O(n)\)인데, 건너는 사람이 2억 명까지 될 수 있다. 20만 × 2억이라 어림없다.

3단계 · 핵심 아이디어

판정 질문: “m번째 친구도 건널 수 있나?” 1단계의 규칙에 따라, 처음 숫자가 m보다 작은 돌은 모두 못 밟는다. 그런 돌이 k개 이상 연달아 있으면 그 구간을 뛰어넘을 수 없다. 그러니 “숫자가 m 미만인 돌이 k개 연달아 있지 않다”면 건넌다.
방향: m이 커지면 못 밟는 돌이 늘기만 한다. 된다…된다 안 된다…안 된다의 최대형이다.
범위: m = 1이면 모든 돌을 밟을 수 있으니 늘 된다(lo = 1). m이 가장 큰 숫자보다 크면 모든 돌을 못 밟으니 안 된다(hi = 가장 큰 숫자).
판정 비용: 돌을 한 번 훑으며 “m 미만인 돌이 몇 개 연달아 있나”를 세면 \(O(n)\)이다.

4단계 · 코드 흐름

판정 함수 ok(m): 연속 개수 run = 0에서 시작한다. 돌이 m 미만이면 run을 1 늘리고, k에 닿으면 거짓. m 이상이면 run = 0. 끝까지 가면 참.
lo = 1, hi = 가장 큰 숫자로 최대형 틀을 돌린다.
lo를 돌려준다.

5단계 · 파이썬 코드

def solution(stones, k):
    def ok(m):                               # m번째 친구도 건널 수 있나
        run = 0
        for s in stones:
            if s < m:                        # m-1명이 지나가면 0 이하가 되는 돌
                run += 1
                if run >= k:
                    return False
            else:
                run = 0
        return True

    lo, hi = 1, max(stones)
    while lo < hi:                           # 최대형 틀
        mid = (lo + hi + 1) // 2             # 올림
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def ok(m):를 solution 안에 두면 stones, k를 인자로 넘기지 않아도 쓸 수 있다.
최대형이라 mid를 올림으로 잡는다. 내림으로 잡으면 lo = hi − 1에서 멈추지 않는다.

6단계 · 실행 추적

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3

lo	hi	mid	m 미만인 돌이 가장 길게 연달아 있는 수	판정	다음
1	5	3	2 (2, 1)	된다	lo = 3
3	5	4	3 (3, 2, 1)	안 된다	hi = 3
3	3				답 3

4번째 친구는 숫자 3, 2, 1인 세 돌이 모두 0이 되어 4칸을 뛰어야 하는데 k = 3이라 못 건넌다.

7단계 · 복잡도와 흔한 실수

판정 \(O(n)\) × 약 log₂(2억) ≈ 28번이다. 돌 20만 개로 재 보니 판정이 늘 끝까지 훑는 입력에서도 0.1초가 안 걸렸다.

친구를 한 명씩 흉내 내 시간 초과가 난다.
“연달아 k개”를 “k − 1개”로 세어 한 칸 어긋난다. 못 밟는 돌이 k − 1개면 k칸을 뛰어 건널 수 있다.
최대형인데 mid를 내림으로 잡아 끝나지 않는다.

다른 풀이도 있다. 판정 질문을 뒤집어 보면 “길이 k인 연속 구간마다 가장 큰 숫자를 구하고, 그중 가장 작은 값”이 답이다. 덱으로 구간 최댓값을 구하면 \(O(n)\)이다. 검증 코드는 이 방법과 결과를 비교한다.

검증: 문제의 예시를 통과했고, 무작위 입력 3,000개에서 “친구를 한 명씩 실제로 건너게 하는” 풀이, “길이 k 구간 최댓값의 최솟값” 풀이와 결과가 모두 같았다. 6단계의 연속 개수와 큰 입력의 시간도 확인했다 — 21_pg64062_p1.py

프로그래머스 스쿨, “징검다리 건너기” (https://school.programmers.co.kr/learn/courses/30/lessons/64062), 2026-09-30 조회. ↩