Kakao: 이 문제만 풀면 면접을 볼 수 있다네
📦 튜플 문제 확인
- 징검다리 건너기 - 2019 카카오 겨울 인턴 코딩테스트 문제 링크
- 입력으로 주어진 배열에는 강가에 있는 디딤돌의 순서대로 숫자가 있습니다.
- 무수히 많은 니니즈 친구들이 한 명씩 디딤돌을 건널 것이며 무조건 가장 가까운 디딤돌을 밟아야합니다.
- 디딤돌을 밟을 때마다 해당 디딤돌의 숫자는 1씩 감소합니다.
- 입력으로 주어진 k값을 초과하여 디딤돌을 뛰어넘을 수 없습니다. 이 때 니니즈의 친구들이 몇명 건널 수 있을까요?
🤔 문제 분석
- 입력으로 주어진 stones 배열의 크기는 1 이상 200,000 이하입니다.
- 문제에 주어진 시나리오대로 니니즈 친구들이 한 명 지나갈 때마다 탐색을 시도하면 O(n^2)의 시간복잡도가 나옵니다.
- 이럴 경우 1억을 초과하는 연산이 필요하므로 다른 방법을 생각해야합니다.
- 선형 자료의 탐색 시간을 줄이는 법은
해시, 이분탐색으로 접근할 수 있습니다.
- 본 문제는
이분탐색 으로 접근하면 해결할 수 있습니다.
✏️ 문제 해결방법
- 니니즈 친구들이 돌을 건널때 돌의 높이는 친구들의
인원 - 돌의 높이가 됩니다. 어느 순간 인원 - 돌의 높이 <= 0이 될 때가 있습니다.
- 이분탐색을 이용해서 연속해서
인원 - 돌의 높이 <= 0가 K 이상이 되면 친구들의 인원을 줄이고 K 미만이 되면 돌을 지나는 친구들의 수를 늘렸습니다.
- 이분탐색의 결과가 최대로 강읠 건널 수 있는 친구들의 인원입니다.
- 이 풀이의 시간 복잡도는 O(nlogm)이 되며, n은 디딤돌의 개수, m은 디딤돌에 적힌 숫자의 최댓값입니다.
- 이분 탐색을 이용해서 디딤돌에 적힌 숫자가 logm의 크기로 줄어들기 때문입니다.
⭕ 최종 풀이
import copy
INF = 200000000
def solution(stones, k):
left = 1; right = INF
while left <= right:
mid = (left + right) // 2
tmp = copy.deepcopy(stones)
for i in range(len(tmp)):
tmp[i] -= mid
cnt = 0
check = False
for i in range(len(tmp)):
if tmp[i] <= 0:
cnt += 1
else:
cnt = 0
if cnt >= k:
check = True
break
if check is True:
right = mid - 1
else:
left = mid + 1
return left
Hope..
지금까지 문제를 잘 풀었다면 놀라운 일이 너와 함께할꺼야 ~
막막한 하루를 보내며 코딩테스트를 준비하는 분들을 응원합니다.