같은 길이의 증가 배열이 있을때, K번째로 작은 원소합 구하기 Q

두 배열이 있을때, 각 배열에서 하나씩 꺼낸 수의 합 중에서 K번째로 작은 원소합을 구해보자.

우선 나이브하게 : N^2 개의 원소가 존재하니 O(N^2) 가 상한이다.

( 합을 전부 나열한 뒤, partition select )

어 이거 근데 문제가 그 양방향 정렬 된 행렬에서 K번째 찾기랑 문제가 같네..!!

4 7 8 11 13

5 9 15 19 21

9 12 13 16 18

12 16 22 26 28

13 17 23 27 29

16 20 26 30 32

18 22 28 32 34

있으면,

이렇게 양방향 증가하는 수열은 왼쪽 끝 아래에서 시작해서, 는 아니였음.. ㅠㅠ

새롭게 관찰하니, 대각선 내의 순서는 정해지지 않지만, 대각선 단계별로 무조건 순서는 강제된다. 왜냐면 좌우 증가기 때문에 대각선 레벨이 달라지면 무조건 커지기 때문,,

그러니까 갯수를 세서, K 보다 작은 N*(N-1)/2 를 찾고 그 차이값을 N개의 숫자 중에서 찾는다 O(N).

그니깐 O(N) 알고리즘이 되는 것..

엌ㅋ 이거 논문을 쓴 내용이네 ㅋㅋㅋㅋㅋ 와 ㅋㅋ 나 좀 쩌는듯..

내가 생각이 안난다는건 실제로 어렵다는거니까 쫄지 말자. 면접관 힌트도 잘 얻고