[Python] BOJ(백준) 20551번 - Sort 마스터 배지훈의 후계자

링크

https://www.acmicpc.net/problem/20551

난이도(solved.ac 참고)

실버4

풀이

실버4라 만만하게 봤는데 생각보다 시행착오를 많이 겪었던 문제였다.

 

일단 이분 탐색을 사용해야 되는 문제였는데, 거기서도 lower_bound라는 개념을 익힐 수 있는 문제였다. lower_bound란 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 이분탐색에서 살짝만 바꿔주면 된다. 물론 당연히 이분탐색의 전제와 같이 sort가 되어있어야 한다.

 

mid를 가운데 값으로 설정하고 target보다 작으면 mid+1로 왼쪽 범위 날리고, target보다 크면 right = mid - 1로 오른쪽 범위 날리고, 같을 경우가 문제다.

[-1, 1, 3, 3, 3, 4, 5, 6, 6]

이런 배열이 있다고 해보자. 3이라는 값을 lower_bound 함수를 돌렸을 경우 구해야 할 답은 2이다. 왜냐면 3이 가장 먼저 나타난 인덱스가 2이기 때문이다.

이분 탐색에서는 mid값이 3(target)이 되면 그대로 그 인덱스를 반환하고 끝마치는데, 여기서는 같을 경우 right = mid를 계속 해줌으로써 while문에서 벗어날 때까지 right의 값을 하나씩 줄여준다. 이렇게 해서 결국 그 target과 같은 값이 가장 먼저 등장하는 인덱스를 찾을 수 있게 되는 것이다.