문제
카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.
- 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
- 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
- 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
- 니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
- 니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
풀이과정
애초에 문제 시작할 때부터 효율성 테스트가 있다고 되어있어서 고민을 좀 오래 했다. 단순히 지나간 니니즈 친구들의 수를 빼서 구할 수도 있었겠지만, 이분탐색을 이용해서 구현해보려고 머리를 좀 굴렸다..🤔
풀이 과정은 이분 탐색으로 s, e를 변경해가며 해결했다. 와중에 check 함수는 mid보다 작은 수의 경우는 0으로 취급하고 cnt를 증가시켜주면서 가장 큰 cnt를 저장한 res가 k보다 크다면 True를 리턴하도록 하였다.
여담으로 두 가지 소스코드를 첨부하였는데, 아래 소스코드가 처음 내가 짠 소스코드이다. 리스트의 모든 값들을 mid와 비교하는 것이 더 오래 걸릴 것이라 생각해서 list comprehension을 통해 mid보다 작은 값들은 0으로 바꿔주고, 0의 개수와 인덱스를 이용해서 check함수의 True/False를 정해주었는데, 이 방법이 오히려 리스트를 생성해나가고 또다시 비교하는 과정에 있어서 더 오랜 시간이 소요되었던 것 같다. 🤨
소스코드
소요 시간 01:15:50
def check(mid, stones, k):
cnt = 0
res = 0
for v in stones:
if v < mid:
cnt += 1
else:
if cnt > res:
res = cnt
cnt = 0
if cnt != 0:
res = cnt if cnt > res else res
return res >= k
def solution(stones, k):
s = 1
e = max(stones)
res = 0
while s <= e:
mid = (s + e) //2
if check(mid, stones, k):
e = mid - 1
else:
res = mid
s = mid + 1
return res효율성 일부통과
def check(stones, k):
answer = [0] * k
counts = stones.count(0)
if counts < k:
return False
save_idx = -1
for i in range(counts):
first_index = stones.index(0, save_idx + 1) # 첫번째 0의 인덱스
if first_index+k <= len(stones) and stones[first_index: first_index+k] == answer:
return True
save_idx = first_index
return False
def solution(stones, k):
answer = -1
right = max(stones)
left = min(stones)
flag = False
while left <= right:
mid = (left + right) // 2
cross = [stone if stone > mid-1 else 0 for stone in stones]
if check(cross, k): #지나갈 수 없으면
right = mid - 1
else: #0이 연속 3개 나왔다.
answer = mid
left = mid + 1
return answer