백준 알고리즘 중앙값 측정 9426번 틀림!

중앙값 측정 실패 풀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	5298	573	376	17.905%

문제

기상학에서 주요 사용하는 대표값은 중앙값이다. (중앙값의 정의는 힌트에 나와있다)

상근이는 1초에 한 번씩 온도를 재는 기계를 가지고 있고, 이 기계에 들어갈 소프트웨어를 작성하려고 한다. 기계에는 작은 디지털 디스플레이가 하나 달려잇다. 매 초마다 디스플레이는 지난 K초동안 측정한 온도의 중앙값을 화면에 보여준다.

상근이는 소프트웨어를 기계에 올리기 전에 컴퓨터에서 테스트해보려고 한다.

총 N초 동안 측정한 온도가 주어졌을 때, 디스플레이에 표시된 중앙값의 합을 구하는 프로그램을 작성하시오. 즉, N개의 수가 주어졌을 때, 길이가 K인 연속 부분 수열 N-K+1개의 중앙값의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N)

둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다.

출력

길이가 K인 모든 연속 부분 수열의 중앙값의 합을 출력한다.

예제 입력 

10 3
3
4
5
6
7
8
9
10
11
12

예제 출력 

60

힌트

수 K개의 중앙값은 ((K+1)/2)번째로 작은 숫자이다. 인덱싱은 1번 부터 시작하며, K가 홀수인 경우를 처리하기 위해 1을 더한다.

예를 들어, (1, 2, 6, 5, 4, 3)의 중앙값은 3이고, (11, 13, 12, 14, 15)의 중앙값은 13이다. 

N, K = map(int,input().split())

list = [0] #초기 값을 받는다.

list2 = [0] #초기 값을 K개의 원소를 갖는 리스트로 만든다.

sum = 0

j = K

if K % 2 == 0:#K가 짝수인 경우

    index = K//2

else:#K가 홀수인 경우

    index = (K+1)//2

for i in range(1, N+1):#인덱스를 1부터 N까지 생성

    list.append(int(input())) #0값 뒤에 입력 값 붙인다.

for i in range(1, N-K+2):#N-K+1번 반복

    for l in range(K):#리스트 크기가 K

        list2.append(list[i+l])#초기 리스트의 값을 K개 만큼 list2에 넣는다.

    list2.sort()#길이가 K인 list2를 정렬한다.

    print(list2)

    sum += list2[index] #중앙값 누적

    j+=1#list의 인덱스를 하나하나 늘림.

    list2 = [0]#list2를 초기화한다.

print(sum)

참고로 위 소스는 출력 초과가 나온다. sort 내장함수를 사용하여 효율적이지 못한 계산을 한 것 같다. 리스트를 2개 만들어 append를 반복한 탓도 있는 것 같다.

 1 2 3 4 5 의 중앙값은 ? 원소의 개수가 홀수 이므로 (개수+1)/2 = 3, 3번째 인덱스의 값 3이다. 10 26 3 98의 중앙값은? 오름차순으로 정렬하면 3 10 26 98이다. 원소의 개수가 짝수이므로 개수/2 = 2, 2번째 인덱스의 값 10이 중앙값이다.

전체 원소를 list에 다 받은 뒤 list2에 K길이만큼의 원소를 이어붙이는 아이디어를 떠올렸다. list에서 K길이의 윈도우를 1칸씩 밀어내며 윈도우 안에 있는 원소를 정렬한 뒤 짝수면 길이를 2로 나눈 값의 인덱스의 원소가 중앙값이 되고 홀수면 길이에 1을 더한 뒤 2로 나눈 값의 인덱스의 원소가 중앙값이 된다.

그러나 출력 초과가 나왔다. 그러므로 좀 더 공부한 뒤 다시 도전해야겠다...