최소 맨해튼 거리, 배열에서 K번째 원소 찾기

*백준 14400: 편의점 2

14400번: 편의점 2

 

맨해튼 거리

• 각 축의 거리는 독립적이다.
• 최소 맨해튼 거리를 갖는 점은 중간점이다 (medoid?)

 

선택 알고리즘을 잊지말자

배열에서 k번째 원소를 찾을 때

1. 정렬 후 k번째 원소 찾기
   : 최선 $O(n)$, 평균 $O(nlogn)$ (Tim sort를 사용하는 V8 엔진 기준)
2. 선택 알고리즘으로 k번째 원소 구하기
   : $O(n)$