[Programmers/ level3] 징검다리 건너기🙄
👩문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오 초등학교의 “니니즈 친구들”이 “라이언” 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. “라이언” 선생님은 “니니즈 친구들”이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다. “니니즈 친구들”은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다. “니니즈 친구들”은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
👩제한사항
- 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
- k는 1 이상 stones의 길이 이하인 자연수입니다.
👩입출력 예
| stones | k | result |
|---|---|---|
| [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] | 3 | 3 |
입출력에 대한 설명은 해당 사이트를 확인해주세요!
🙋♀️접근 방법
우선 효율성 다 따지지 말고 가장 떠올리기 쉬운 방식부터 생각해보자!
☝️ 가장 쉽게 생각할 수 있는 방법
- 한 사람이 건널 때마다 배열의 값들을 1씩 감소시킨다.
- 더 이상 건너지 못할 때까지 반복하여 최종 사람 수를 구한다.
🙄 그렇다면 이렇게 했을 때 시간복잡도는 어떻게 될까?
- 배열의 최대 크기 * 배열 원소의 최대값 = 20만 * 2억 -> 해당 방식으로는 효율성을 통과하지 못하게 된다.
그 다음으로 내가 시도한 방식은 다음과 같다. 코드를 통해서 그 방식을 살펴보자!
✌️ 살짝 나아진 효율성!
def solution(stones, k):
m = 200000000
size = len(stones)
for i in range(size): #stones[i]명의 사람이 건널 경우
tmp = 1
if stones[i] >= m:
continue
for l in range(i-1, max(-1, i-k), -1): #i 이전 징검다리에서 0이 되는 돌의 수
if stones[i] >= stones[l]:
tmp += 1
else:
break
if len(stones)-i-1+tmp < k: # i 이후 모든 징검다리가 0이 되더라도 k개가 안되는 경우
continue
for j in range(i+1, min(i+k, size)): #i 이후 징검다리에서 0이 되는 돌의 수
if stones[i] >= stones[j]:
tmp += 1
else:
break
if tmp >= k: #stones[i]명이 건널 경우 연속해서 뛰어야 하는 징검다리수가 k보다 크거나 같을 경우
m = min(m, stones[i])
return m
즉, 정리하면 다음과 같다.
- 배열의 값 = 건너는 사람의 수라고 가정!!
- 배열을 돌며 해당 숫자의 사람이 건널 경우, 모두 건널 수 있는 지를 판단한다.
- 배열 i번째를 확인할 경우
- 건너는 사람의 수 = stones[i]
- i에서 +/-k 사이의 값들을 확인해 stones[i]보다 작은 값인지를 확인!
- 작을 경우, stones[i]명이 다리를 건넌다면 그 돌의 값은 0 이하가 된다.
- 연속해서 0 이하가 되는 징검다리 수를 계산해 k와 비교하여 최소 m 값을 계산한다.
- 배열 i번째를 확인할 경우
🙄 그렇다면 위 알고리즘의 시간복잡도는 어떻게 될까?
- 배열의 최대 크키 * k의 최대 크기 = 20만 * 20만
물론 위 1번 알고리즘보다는 시간복잡도가 나아졌지만 효율성 두 개를 통과하지 못한다.
👌해답은 이분탐색!
처음 나는 이 문제에 어떻게 이분탐색을 적용하지 싶었다. 이분탐색을 적용하기 위해서는 배열이 정렬되어 있어야 하는데, 그렇게 된다면 문제 자체가 망가지기 때문이다. 내가 잘못 생각했던 부분은 무조건 배열에서 이분탐색을 진행해야 한다고 생각했던 점이다!!
⭐우리가 구할 것은 몇 명이 건널 수 있는지다!⭐ 그렇다! 우리는 건널 수 있는 사람의 수의 범위에서 이분탐색을 진행하면 된다!
🙄 시간복잡도?
- 사람 수 범위 = stones 값 범위
- log(2억) = 27-28
그렇다면 이제 코드를 작성해보자! 이분탐색을 적용한다면 정말 쉽게 문제가 해결된다!
🙋♀️알고리즘
def solution(stones, k):
start = 1
end = max(stones)
while start <= end:
mid = (start+end)//2 # mid번째 사람이 건널 수 있는지를 판단하게 된다.
count = 0
for i in stones:
if count < k:
if i-mid <= 0:
count += 1
else:# 0이하가 아닌 징검다리를 만났으므로 count를 초기화한다.
count = 0
else:
break
if count < k:# mid번째 사람이 건널 수 있으므로 mid 이상의 사람이 건널 수 있는지를 판단한다.
start = mid+1
else: # mid번째 사람이 건너지 못하므로 mid 이하에서 건널 수 있는 최대 인원을 구한다.
end = mid-1
result = mid
return result
🙇♀️풀이에 부족한 부분이 있다면 말씀해주세요! 감사합니다!
댓글남기기