프로그래머스 <징검다리 건너기>

프로그래머스 <징검다리 건너기>

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

프로그래머스

---

징검다리 건너기

"니니즈 친구들"이 "라이언" 선생님과 징검다리가 있는 개울을 건너려고 한다.

징검다리를 건널 수 있도록 다음과 같은 규칙을 만들었다.

일렬로 놓여있는 각 징검다리의 디딤돌에는 모두 숫자가 적혀있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어든다.

디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며, 그 다음 디딤돌로 한 번에 여러 칸을 건너 뛸 수 있다.

단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있다.

무제한인 "니니즈 친구들"이 최대 몇 명까지 징검다리를 건널 수 있는지 구하여라.

 

징검다리를 건너야 하는 니니즈 친구들의 수는 무제한이라고 간주한다.

stones 배열의 크기는 1 이상 200,000 이하 이다.

stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수이다.

k는 1 이상 stones의 길이 이하인 자연수이다.

---

문제해결

stones 배열 각 원소들의 값이 최대 200,000,000이기 때문에 이분탐색을 먼저 고려했다.

이분탐색으로 징검다리를 건너는 친구들의 수를 찾아내는 방법으로 문제를 풀이했다.

 

start를 0으로 end를 200,000,000으로 하여 이분탐색을 진행하였다.

mid 값을 구해 mid 명 수가 징검다리를 건널 수 있는지 확인하는 check 함수를 구현하였다.

check 함수에서는 stones 배열의 각 원소에서 mid 값을 빼서 징검다리의 디딤돌이 살아있는지 판단하였다. 만약 k개 연속으로 디딤돌이 없다면 건널 수 없기 때문에 False를 반환하고 k 개 미만이라면 True를 반환하였다.

이때 mid 값을 뺐을 때 디딤돌이 없는 경우가 k개 미만이기 때문에 1명은 더 건널 수 있어서 mid + 1명이 징검다리를 건널 수 있다.

check 함수의 값이 True라면 answer 값을 update하고 mid값이 더 커질 수 있게 start = mid + 1로 해주었다.(우리는 최대값을 찾는 것이기 때문에 mid값이 제일 커질 때 까지 한다.)

만약 False라면 mid값이 작아질 수 있게 end = mid - 1로 해주었다. 

---

코드

def solution(stones, k):
    answer = 0
    start = 0
    end = 200000000
    while start <= end:
        mid = (start + end) // 2
        if check(stones, k, mid):
            answer = max(answer, mid+1)
            start = mid+1
        else:
            end = mid-1
    return answer

def check(stones, k , num):
    acc = 0
    for n in stones:
        if (n-num) <= 0:
            acc+=1
            if acc >= k:
                return False
        else:
            acc = 0
    return True;

---

check 함수에서  for문을 돌릴 때, in range()를 사용해 temp = stones[n] - num을 이용한 경우와 in 리스트를 사용한 경우를 비교해봤을 때 in 리스트를 사용한 경우가 효율성 테스트케이스를 모두 통과할 수 있었다.

stones[n]으로 참조를 계속 해야 해서 그런 것 같다.

---

결과

---