백준 1300: K 번째 수 (Swift)

 

이진탐색( Binary Search )의 확장판인 Parametric Search로 해결해야하는 문제이다. 

Parametric Search를 생각해내는 것 뿐만 아니라, 그 내부 구현까지 매우 난이도가 높은 문제라고 생각한다.

 

배열에 존재할 수 있는 1 ~ n * n까지의 수 범위에서 이분탐색하며, 현재 mid에 위치하는 숫자에 i 대하여, 

(i를 포함함에 주의) i 이하의 숫자가 배열에 몇 개 존재하는지 its_order()함수에서  return해준다.

 

주의해야 할 점이 두가지 있다!!

1. n = 3인데, i = 7인 경우와 같이 없는 숫자가 매개변수로 전해지는 경우

2. k = 7인데, 1 2 2 3 3 4 6 6 9 과 같이 its_order()의 리턴값이 7은 절대 나올 수 없는 경우 ( 같은 숫자가 이어져서.. 6 혹은 8만 나옴)

 

(A) 1번이고 2번이고 상관 없이 its_order()의 return 값이 target보다 작다면, 어쨌든 숫자는 커져야한다.

따라서 29 ~ 31번 줄과 같이 start = mid + 1 처리 해주고 while문을 이어간다.

 

(B) 만약 now (its_order()의 return 값) == target 인 경우에는, 

mid값이 정확히 k번째에 위치하는 숫자일 수도 있지만, 1번 경우와 같이 실상 mid보다 작은 숫자가 배열 내 k번째 숫자인데 now == target이 되는 상황이 발생할 수 있다. 

=> 이 때는 사실 last에 기록해두지 않고, end = mid - 1 해주면, 추후에 다시 now == target인 mid값을 찾을 수 있게 된다.

( mid 값이 정확히 k번째에 위치하는 숫자일 때는 last = mid로 기록해 주어야 할 것이다.)

 

(C) 마지막으로, now > target 인 경우에는 어떻게 할까? 

단순히 더 작은 숫자를 탐색해야하므로, end = mid - 1만 처리해주는 것으로 생각할 수 있지만, 

(a) - k  = 5 이고 mid = 5로 탐색하였을 때, 1 2 3 3 5 5 5 6 과 같이 5번째 ~ 7번째 숫자가 모두 같아, 사실 우리가 찾은 mid값이 k번 째 숫자가 맞지만, 

now > target이 되어버리는 상황이 벌어질 수 있다.

(b) -물론  k = 5 이고 mid = 7로 탐색하였을 때, 1 2 3 4 5 6 7과 같이 end = mid - 1 해주고 넘어가야하는 경우도 있다.

하지만 (a)경우를 처리해주기 위해 end = mid - 1과 함께 last = mid를 처리해주었다. (코드 26 ~ 27)

 

따라서 (B), (C)를 종합한 코드가 25 ~ 28 째 줄이다.

( 복기를 하면서도 참 어려운 문제임을 깨닫게 된다...)