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

 문제

 

programmers.co.kr/learn/courses/30/lessons/64062

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

 

 문제 상황

 

- 징검다리 배열이 주어지고 한명이 건널 때마다 돌다리의 숫자가 1씩 감소한다. 0이 되면 더이상 감소하지않지만 한번에 건널수 있는 길이가 k로 정해져있어 최대로 건널 수 있는 사람 수를 구한다.

 

 

 

 해결 전략

 

- 최초에는 배열을 순회하며 1씩 줄이고 사람 수를 1씩 증가시켰다. 즉, 한사람씩 관찰하였는데 문제가 사람 수는 무제한이고 돌다리는 최대 2억번까지 가능하므로 이러면 연산을 최소 2억번 해야한다.

 

- 범위가 2억번이므로 최소 O(NlogN) 이하의 속도에서 검색할 필요가 있다.

 

- 최대 건널 수 있는 사람 수는 stones의 최대값을 넘어설 수 없다. 그래서 0명과 최대값 사이에서 이진탐색하며 그 숫자의 사람이 건널 수 있는지를 확인한다. 즉, 탐색하는 내용이 사람 수가 된다.

 

 

 

 코드

 

def check(stones,k,mid):
    # 연속으로 0의 개수가 얼마인지 확인
    cnt = 0
    for stone in stones:
        stone -= (mid-1)
        if stone <= 0: 
            cnt += 1
            if cnt == k:
                return False
        else:
            cnt = 0
    return True
 
def solution(stones, k):
    start = 0
    end = max(stones)
    while True:
        mid = (start+end)//2
        # 만약 mid만큼의 사람수가 건널 수 있다고 하면
        if check(stones, k, mid):
            start = mid
        else:
            end = mid
        if end-start <= 1:
            return start if not check(stones,k,end) else end
 
print(solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))
 
# 정확도만 통과
 
# def check(stones, k):
#     num = 0
#     for i in range(len(stones)):
#         if stones[i] == 0 :
#             num += 1
#             if num == k:
#                 return True
#         else:
#             num = 0
#     return False
 
    
# def solution(stones, k):
#     cnt = 0
#     while True:
#         # 0이 존재하는지 확인
#         # 0*k가 stones에 존재하면 종료
#         if check(stones,k,0,len(stones)-1):
#             return cnt
#         # 존재 안하면 한번씩 더 빼주기
#         for i in range(len(stones)):
#             if stones[i] != 0: stones[i] -= 1
#         cnt += 1
 

 

 

 

 해설

 

- 최초의 방법은 O(N)라고 생각하였지만 사람 수만큼 순회해야 하므로 정확히는 O(N*M)이 되어 효율성을 통과하지 못했다.

 

- 이진탐색을 생각했지만 그 적용을 0의 개수를 찾는데에서만 생각하다가 실패하였다.

 

 

 

 새로 학습한 것 & 실수 

 

- 문제를 풀 때에 한 번 생각이 고정되면 바꾸기가 어렵다. 문제의 경우 0의 개수를 탐색하는 것만 이진탐색으로 풀려다가 실패하였다.

 

- 탐색 자체는 선형 순회하면서 후보군을 이진 탐색하는 역발상을 할 필요가 있었다.

 

- 특히 마지막에 start를 반환한 이유는 start가 0이 아닐 경우 무조건 start만 반환하면 됬는데 start가 0이되면 end가 1일 때에 1이 반환이 안된다. 그래서 테스트 케이스 1번을 통과하지 못했지만 경계값을 기준으로 검사하여 오류를 발견했다.