글 읽기 - 9426 - 중앙값 측정 질문입니다.

occidere 5년 전 0

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

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

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

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

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

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

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		String tmp = in.readLine();
		int i, n = Integer.parseInt(tmp.substring(0, tmp.indexOf(" "))), k = Integer.parseInt(tmp.substring(tmp.indexOf(" ")+1));
		
		/*원본 배열 arr과, k개만 따로 저장할 부분배열  subArr 선언 */
		int []arr = new int[n], subArr = new int[k];
		for(i=0;i<n;i++) arr[i] = Integer.parseInt(in.readLine());
		
		long sum = 0; //최대 들어올 수있는 값이 250,000 * 65535 = 16383750000이므로 long으로 선언
		int len = n-k+1, m = k%2!=0?k/2:k/2-1;//반복할 길이 len = n-k+1, 중간값 m
		
		/*k개만큼만 subArr에 복사 후 정렬해서 중간값을 sum에 더해줌*/
		for(i=0;i<len;i++){
			subArr = Arrays.copyOfRange(arr, i, i+k);
			Arrays.sort(subArr);
			sum+=subArr[m];
		}
		out.write(String.valueOf(sum));
		out.close();
		in.close();
	}
}

dlwodnsdl 5년 전 2

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

occidere 5년 전 0

친절한 설명 감사합니다!

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

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

cycho21 5년 전 2

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

occidere 5년 전 0

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

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

문제

문제

출처

ICPC

9426 - 중앙값 측정 질문입니다.

occidere 5년 전 0

dlwodnsdl 5년 전 2

occidere 5년 전 0

cycho21 5년 전 2

occidere 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말