[프로그래머스] 징검다리 - 파이썬(Python3)
프로그래머스 level 4 징검다리
-> programmers.co.kr/learn/courses/30/lessons/43236
코딩테스트 연습 - 징검다리
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가
programmers.co.kr
이 문제는 프로그래머스에 있는 징검다리 문제입니다.
level4라서 꽤 어려워보이지만, 쉬운 편입니다!
문제 읽어보시고, 같이 풀어볼게요!
풀이 아이디어
먼저 distance 범위가 저러니까.. 무조건 이분탐색인것 같네요.
핵심은 이분탐색인걸 아는게 첫번째입니다.
그러면 뭘 탐색해야하느냐면, 거리의 최솟값을 탐색하면 됩니다.
그러다가 우리가 원하는 값을 찾으면 리턴해주면 되겠죠.
여기서 거리의 최솟값을 탐색하는데, 이 최솟값을 가지고
뭘 해야할지를 생각하는 것이 중요합니다.
우리는 탐색할 값이 정답이라고 생각하고,
이 탐색할 값에 맞춰서 문제를 풀고,
그 답이 문제의 조건에 맞는지 살피는게 이분탐색 문제의 핵심입니다.
이렇게 말하면 알아들을 사람이 없을 것 같으니, 구현에서 더 자세히 다뤄보겠습니다.
구현
먼저 start는 1로, end는 distance//(len(rocks)-n+2)+1로 해줍니다!
왜냐면 rocks에서 n개를 잘랐는데
그게 정확히 똑같은 간격으로 떨어져있을때가 최대이기 때문입니다.
그리고 start와 end를 갱신하면서 mid값을 문제의 답이라고 생각하고
바위를 제거해보면 됩니다.
문제에 나온 예로 설명해드리겠습니다.
먼저 rocks를 정렬하면
[2, 11, 14, 17, 21]입니다.
그리고 start = 1, end = 6이 됩니다.
그럼 처음 mid는 (1+6)//2 == 3에서 3입니다.
3을 답이라고 생각한 뒤에, 돌다리를 건너보겠습니다.
움직일때 최소 3칸 이상씩 뛰도록 하면 됩니다.
그럼 0에서 2는 2칸이니까 못가고, 바로 11, 그다음은 14...
즉 [0, 11, 14, 17, 21, 25] 와 같이 움직이게 됩니다.
그럼 여기서 도달하지 않은 돌의 개수를 세어주면 됩니다.
2만 도달하지 않았으므로 1개겠죠? 이게 바로 문제에서 주어진
n과 대응하는 수가 됩니다.
3이 답이라고 생각하고 돌다리를 뛰면, 문제에서 요구한 n보다 작은 값이 나옵니다.
그러므로 3은 답이 아니고,
3이라고 했을때 이때 지우는 돌의 개수가 n보다 작으므로 진짜 답은 3보다 큰 값이 나올 수 있습니다.
그러므로 s = mid+1로 해주어서 더 많이 건너뛸 수 있도록 해줍니다.
만약 지우는 돌의 개수가 n보다 크다면, e = mid-1로 바꿔주면 되겠죠.
이렇게 계속 반복해서 문제를 풀 수 있습니다.
아래에 코드를 첨부합니다!
def solution(distance, rocks, n):
rocks.sort()
s = 1
e = distance//(len(rocks)-n) + 1
answer = 0
while s<=e:
mid = (s+e)//2
t_rocks = list(rocks)
temp = delete(t_rocks, n, mid, distance)
if temp:
answer = mid
s = mid+1
else:
e = mid-1
return answer
def delete(rocks, n, mid, distance):
s = 0
nodel = []
for i in range(len(rocks)):
if rocks[i] - s >= mid:
nodel.append(i)
s = rocks[i]
if distance - s >= mid:
nodel.append(len(rocks)-1)
count = len(rocks) - len(nodel) + 1
print(mid, count)
if count > n:
return False
else:
return True