[BOJ] 기타 레슨 in Python & Kotlin

문제풀러 가기!

우선 이문제 참... 하하...
많은 걸 알게되는 문제인 것 같습니다.

일단 이분탐색 문제를 최근들어서 풀지 않았었는 데, 이번 기회에 다시 복습해서 다행이네요. 이런 문제가 기업 코테에 나온다고 생각하면 아마 못풀지 않았을까 생각들어서 그런지 정말 다행입니다.

저는 처음에 이 문제를 접근할 때 어떻게 해야 하나 큰 고민을 했습니다. 그러니까. 결국에는 무엇을 탐색해야 하는지 몰랐기 때문에 이분 탐색 알고리즘을 알아도 코드를 작성하지 못했던 문제였습니다.

이분 탐색 문제의 경우 알고리즘을 알고 있다고 해도 무엇을 탐색해야 할지 명확하게 알고 있어야 문제를 접근하고 풀 수 있으니, 이점을 유의해야 한다.

제가 생각했던 풀이 방식은 partition이었습니다. 문제에서 주어진 partition을 모두 만들어서 해당 partition에 대해 이분 탐색을 진행하면 풀리지 않을까? 생각했던 문제였습니다. 하지만, 생각해보면 파티션 공식을 실버 1 난이도에 적용하는 것은 너무 범위에 넘어가기도 했고 그리고 무엇보다 해당 공식을 모르고 있었거든요. 그렇다고 제가 알고리즘을 만들자 생각을 하다보니 애초에 입력값이 크기 때문에 무조건 시간 초과가 난다는 생각으로 인해 절대 partition으로 풀 문제가 아니라고 생각했습니다. 그렇기 때문에 풀이를 살펴봤는데 문제에서 주어진 블루레이라는 것에 초점을 맞추고 이분 탐색을 진행하면 된다는 아이디어를 얻고 금방 이해할 수 있었습니다.

아래는 파이썬 풀이입니다.

아래는 코틀린 풀이입니다.