99클럽 코테 스터디 22일차 TIL - 43236 징검다리

43236. 징검다리 / c++ / level4 / 2시간+

문제 및 코드

접근 방식

이분탐색

1. 결론은 돌을 n개 이하로 제거했을 때, 시작점(0), 각 다리 사이의 거리, 끝점(distance)가 모두 x이상일 때, 이 x에 들어갈 수 있는 수 중 가장 큰 값을 구하는 문제였다.
2. 이분탐색을 안쓰고 정렬이랑 우선순위큐를 써서 풀어보려고 시간을 엄청 썼다.
3. 결국 이분탐색으로 풀었는데, AI가 무슨 시작점과 끝점은 상관 없고, 각 돌 사이의 거리만 구하라고 해서, 내가 문제를 잘못 읽었나보다 하고 그렇게 풀었는데, 틀렸다.
4. 다시 결과를 보니 내가 원래 읽었던 게 맞았다. 프로그래머스 AI는 문제가 많아 보인다.
5. 마지막 돌과 distance까지의 거리를 어떻게 구할까 고민했는데, (그 돌이 제거됐는지에 따라 달라지므로)
6. 그냥 매번 비교할 때, 이전돌과의 거리 & distance와의 거리가 모두 mid 이상인지 체크하고, 아니면 제거하면 됐었다. (이걸 생각해내기까지 또 오래 걸렸다.)

생각해 볼 점

1. level4 문제는 맛있다. 그런데 너무 오래 걸려서 붙잡고 있다보면 시간이 사라진다.
2. 그래도 계속 풀다보면 익숙해지고 점차 속도가 붙지 않을까 생각하고 있다.
3. 99클럽 덕분에 기존에는 잘 도전하지 않던 문제들도 많이 접하게 돼서 도움이 된다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL