[파이썬 python] 프로그래머스 - 징검다리 건너기

• 징검다리 건너기

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

---

[입출력 예]

stoneskresult

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

3

3

입출력 예에 대한 설명

---

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

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

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

---

def solution(stones, k):
    answer = 0
    # 끝은 stones 에서 최댓값으로 설정하였다.
    start, end, mid = 1, max(stones), 0
	
    # 시작이 끝보다 커지면 반복문을 빠져나온다.
    while start <= end:
    	# 중간을 설정한다.
        if (start+end) % 2 == 0:
            mid = (start+end) // 2
        # 굳이 반올림을 했지만 필요없는 듯 하다.
        else:
            mid = ((start+end) // 2)+1

        cnt, max_cnt = 0, 0
        # 돌들을 하나씩 탐색한다.
        for i in range(len(stones)):
        	# 돌이 중간(현재 건너는 사람 수) 보다 작다면
            if stones[i] - mid <= 0:
            	# cnt 해준다
                cnt += 1
                max_cnt = max(max_cnt, cnt)
                # 최대 cnt가 k(디딤돌의 최대 칸수) 보다 크거나 같다면 빠져나온다.
                if max_cnt >= k:
                    break
           # 돌이 중간보다 크면 cnt를 초기화(0) 시켜줌.
            else:
                cnt = 0
        # 최대 cnt가 k보다 작다면, 건너는 사람 수는 더 커져야 하므로, start를 늘려준다.
        if max_cnt < k:
            start = mid + 1
        # 최대 cnt가 k보다 크다면, 건너는 사람수는 더 작아져야 하므로, end를 줄여준다.
        # (물론 위에 최대 cnt가 k보다 크다면 바로 빠져나와서 클 일은 없지만, 개념적으로!)
        # 최대 cnt가 k랑 같다면, 건너는 사람수는 정답이거나 더 작으므로, end를 줄여준다.
        elif max_cnt >= k:
            end = mid - 1
	
    # 이진 탐색을 다 빠져나온 후 start가 정답.
    answer = start
    return answer

 

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.06ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (1.20ms, 10.2MB)
테스트 7 〉	통과 (2.38ms, 10.3MB)
테스트 8 〉	통과 (3.23ms, 10.3MB)
테스트 9 〉	통과 (3.59ms, 10.2MB)
테스트 10 〉	통과 (0.05ms, 10.2MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (0.06ms, 10.2MB)
테스트 13 〉	통과 (0.10ms, 10.2MB)
테스트 14 〉	통과 (0.67ms, 10.2MB)
테스트 15 〉	통과 (3.36ms, 10.3MB)
테스트 16 〉	통과 (2.33ms, 10.2MB)
테스트 17 〉	통과 (2.45ms, 10.2MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.07ms, 10.2MB)
테스트 20 〉	통과 (0.15ms, 10.2MB)
테스트 21 〉	통과 (1.16ms, 10.2MB)
테스트 22 〉	통과 (1.61ms, 10.3MB)
테스트 23 〉	통과 (3.86ms, 10.2MB)
테스트 24 〉	통과 (2.48ms, 10.2MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (815.62ms, 18.5MB)
테스트 2 〉	통과 (958.31ms, 18.6MB)
테스트 3 〉	통과 (953.04ms, 18.7MB)
테스트 4 〉	통과 (282.02ms, 18.6MB)
테스트 5 〉	통과 (305.32ms, 18.5MB)
테스트 6 〉	통과 (385.47ms, 18.5MB)
테스트 7 〉	통과 (1117.22ms, 18.6MB)
테스트 8 〉	통과 (1159.35ms, 18.5MB)
테스트 9 〉	통과 (1104.07ms, 18.6MB)
테스트 10 〉	통과 (1147.12ms, 18.5MB)
테스트 11 〉	통과 (1024.66ms, 18.6MB)
테스트 12 〉	통과 (1167.93ms, 18.5MB)
테스트 13 〉	통과 (438.64ms, 18.7MB)
테스트 14 〉	통과 (315.59ms, 18.6MB)

 

• 후기
• 시간 효율이 필요하고, 입력값이 어마어마하며, 탐색하는 값이 선형구조 인 것 같다? 이진탐색이다! 
• 사실 살짝 완벽히는 이해가 안되서 다시 봐야 할 듯하다. 헷갈린다.

 

• 풀이
• (1) 시작, 중간, 끝을 설정한다. 시작이 끝보다 커지면, 답을 구할 수 있으며 반복문을 탈출한다.
• (2) mid(현재 생각하는 건널 수 있는 사람 수) 와 stones의 돌을 비교한다. mid - stone을 할 경우에 0과 같거나 음수가 나온다면, cnt += 1 해준다. 지금까지 cnt 중 최대인 cnt도 구한다.
• (3) mid - stone을 해서 양수가 나온다면, cnt를 0으로 초기화.
• (4) 최대cnt가 k보다 작다면, 건너는 사람 수는 더 커져야 하므로, start를 mid+1로 늘려준다.
• (5) 최대cnt가 k보다 크거나 같다면, 건너는 사람 수는 더 작을 수도 있으므로, end를 mid-1로 줄여준다.
• (6) 이진탐색이 끝난 뒤 start가 정답.

 

• 예시
• stones = [2, 11, 3, 4] 이며, k (디딤돌 최대 칸수) = 2 일 경우
• start=1, mid=6, end=11  ==>  mid와 stones 비교하기 [-4, 5, -3, -2]  ==> 0이하가 연속된 최대 길이는 2
• 길이 2 >= k 이므로, mid는 더 작을 수도 있다. end를 mid-1로 줄여준다.
• start=1, mid=3, end=5  ==>  mid와 stones 비교하기 [-1, 8, 0, 1]  ==> 0이하가 연속된 최대 길이는 1
• 길이 1 < k 이므로, mid는 더 커야 한다. start를 mid+1로 늘려준다.
• start=4, mid=5, end=5  ==>  mid와 stones 비교하기 [-3, 6, -2, -1]  ==> 0이하가 연속된 최대 길이는 2
• 길이 2 >= k 이므로, mid는 더 작을 수도 있다. end를 mid-1로 줄여준다.
• start=4, mid=4, end=4  ==>  mid와 stones 비교하기 [-2, 6, -1, 0]  ==> 0이하가 연속된 최대 길이는 2
• 길이 2 >= k 이므로, mid는 더 작을 수도 있다. end를 mid-1로 줄여준다.
• start=4, mid=4, end=3  ==>  start > end 이므로 return.  답은 start = 4