occidere   1년 전

문제에 주어진 조건대로 맞춰서 단순하게 풀어보니 시간초과를 피할 수가 없네요...

제가 푼 방식은 이렇습니다.

  1.  주어진 N개의 온도값을 담을 배열과는 별도로, 크기가 k인 부분배열 subArr[k]를 선언합니다.

  2. 원본 배열은 정렬되면 안되므로, 0부터 n-k+1까지 반복문을 통해 돌리며, subArr에 i부터 i+k 만큼(=k개)의 값들을 Arrays.copyOfRange를 이용해서 저장하고, 이 subArr 배열을 정렬(Arrays.sort)합니다.

  3. 정렬된 subArr의 중앙값을 sum에 더합니다. 

시간초과가 날 것이라고 어느정도 예상은 하고 있었으나, 막상 진짜로 시간초과가 나버리니 어떤 방법으로 해야될지 도저히 감이 안오네요 ㅠㅠ

혹시 시간초과를 줄일 수 있는 다른 접근방식이 있나요? 아니면 이 접근방식 자체가 틀렸다면 어떻게 접근하면 좋을까요...?

고수님들의 답변 부탁드립니다. ㅠㅠ

dlwodnsdl   1년 전

중앙값 이진트리를 만들면 되지 않을까요 root를 중앙값으로 하고 루트의 왼쪽은 중앙값보다 작거나 같으면서, 부모노드가 자식노드보다 크거나 같게 만들고, 루트의 오른쪽 애들은 중앙값보다 크면서 부모노드가 자식노드보다 작거나 같게 만든 다음에, 경우의 수에 따라서 트리를 조작해주면 O(NlogK)시간 복잡도내에 해결이 가능합니다

occidere   1년 전

친절한 설명 감사합니다!

트리 공부를 안했는데 이렇게 당할 줄은 몰랐네요 ㅠㅠ

공부를 조금 더 해보고 다시 도전해보도록 하겠습니다!..

cycho21   1년 전

아직 못 푸셨다면 Quick Selection 으로 해결해보세요~

occidere   1년 전

답변 감사합니다! 좀더 공부해서 도전해보도록 하겠습니다!

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