qopwer4345   2년 전

preview

한코드씩 풀어봤습니다

while문 안의 for문에서 위의 (n*n) 행렬에서 i행을 기준으로 mid값보다 작은 값들을 cnt에 더해주는 이유는

각 행마다 key값보다 작은 값들의 숫자를 세어서 k번째 숫자를 찾는 것이 목적인가요?

우선 제가 이해한 바를 설명드리겠습니다

예제에 제시된 n*n 행렬 A를 B수열로 치환후 정렬하면 {1, 2, 2, 3, 3, 4, 6, 6, 9} 가 됩니다.

위의 cnt가 8이 된것은 6보다 작거나 같은수가 총 8개 이므로 mid값이 중복될 수 있을 가능성을 고려해

cnt가 k보다 높아도 mid값을 결과로 치며 여기서 mid는 배열의 idx가 아닌 배열에 담겨있는 요소의 크기를 의미한다.

가 제대로 이해한건가요?

qopwer4345   2년 전

저기서 end 값을 요소의 제일 큰 값인 n*n로 해도 되지만 그럴경우 n이 10^5 k가 n보다 한없이 작게 나올 경우 쓸대없는 연산을 많이 하게 되어서 시간초과가 날까봐 한계점을 k로 잡았습니다.

결과적으로 우리는 배열에서 기준점인 mid라는 값보다 몇개 작은수가 있는지 중요하기에 첫번째 지점과 k의 중간지점을 mid로 지정하면 시간적 이득을 볼 수 있다고 생각했습니다.

댓글을 작성하려면 로그인해야 합니다.