9426번 - 중앙값 측정
문제에 주어진 조건대로 맞춰서 단순하게 풀어보니 시간초과를 피할 수가 없네요...
제가 푼 방식은 이렇습니다.
1. 주어진 N개의 온도값을 담을 배열과는 별도로, 크기가 k인 부분배열 subArr[k]를 선언합니다.
2. 원본 배열은 정렬되면 안되므로, 0부터 n-k+1까지 반복문을 통해 돌리며, subArr에 i부터 i+k 만큼(=k개)의 값들을 Arrays.copyOfRange를 이용해서 저장하고, 이 subArr 배열을 정렬(Arrays.sort)합니다.
3. 정렬된 subArr의 중앙값을 sum에 더합니다.
시간초과가 날 것이라고 어느정도 예상은 하고 있었으나, 막상 진짜로 시간초과가 나버리니 어떤 방법으로 해야될지 도저히 감이 안오네요 ㅠㅠ
혹시 시간초과를 줄일 수 있는 다른 접근방식이 있나요? 아니면 이 접근방식 자체가 틀렸다면 어떻게 접근하면 좋을까요...?
고수님들의 답변 부탁드립니다. ㅠㅠ
친절한 설명 감사합니다!
트리 공부를 안했는데 이렇게 당할 줄은 몰랐네요 ㅠㅠ
공부를 조금 더 해보고 다시 도전해보도록 하겠습니다!..
아직 못 푸셨다면 Quick Selection 으로 해결해보세요~
답변 감사합니다! 좀더 공부해서 도전해보도록 하겠습니다!
댓글을 작성하려면 로그인해야 합니다.
occidere 5년 전
문제에 주어진 조건대로 맞춰서 단순하게 풀어보니 시간초과를 피할 수가 없네요...
제가 푼 방식은 이렇습니다.
1. 주어진 N개의 온도값을 담을 배열과는 별도로, 크기가 k인 부분배열 subArr[k]를 선언합니다.
2. 원본 배열은 정렬되면 안되므로, 0부터 n-k+1까지 반복문을 통해 돌리며, subArr에 i부터 i+k 만큼(=k개)의 값들을 Arrays.copyOfRange를 이용해서 저장하고, 이 subArr 배열을 정렬(Arrays.sort)합니다.
3. 정렬된 subArr의 중앙값을 sum에 더합니다.
시간초과가 날 것이라고 어느정도 예상은 하고 있었으나, 막상 진짜로 시간초과가 나버리니 어떤 방법으로 해야될지 도저히 감이 안오네요 ㅠㅠ
혹시 시간초과를 줄일 수 있는 다른 접근방식이 있나요? 아니면 이 접근방식 자체가 틀렸다면 어떻게 접근하면 좋을까요...?
고수님들의 답변 부탁드립니다. ㅠㅠ