프로그래머스. 징검다리 건너기

tose33 2022. 1. 14. 22:00

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

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

programmers.co.kr

처음에 dp로 풀어봤다.

연속된 k개의 숫자중 가장 큰 값을 찾고, 그 중 가장 작은값이 답이다.

그런데 딱 하나의 테스트케이스가 시간초과가 났다.

아마도 시간제한이 1s 인가보다.

다른 알고리즘을 고민해 봐야겠다 ...

위의 방법으로는 해결이 안되서 결국 이분탐색으로 풀었다.

위 방법으로 푸는 도중에 이분탐색인것 같긴했는데 테스트케이스 13빼고는 매우 빠른 속도를 보여줬으므로 어떻게 알고리즘을 개선하면 통과하지 않을까 여러가지 방법을 써봤는데 결국 실패.

이분탐색은 건널수 있는 사람을 기준으로 구했다.

건널수 있는 최소 사람수 = 1명, 최대 사람수 = stones 배열에서의 최댓값, mid = (최소 사람수 + 최대 사람수) / 2

mid명이 건널수 있는지 없는지 판단은 stones 배열에서 mid보다 작은 값이 k개 이상 연속되면 mid명은 건너는게 불가능하다.

예를들어 3명이 건널수 있는지 판단한다고 하고 stones 배열이 아래와 같다면

한 사람이 건너면 모든 돌들의 수가 1씩 줄어든다.

따라서 정확히말하면 stones[i] - mid명이 0이 되는 연속된 돌의 수가 몇개인지가 중요하다.

2022.01.18