Statistics from a Large Sample

https://leetcode.com/problems/statistics-from-a-large-sample/

Statistics from a Large Sample - LeetCode

256 길이의 List를 주고
List의 item에서 index값은 값이고 value는 그 값의 갯수를 의미한다

[0,1,2,1] = 1이 1개, 2가 2개, 3이 1개란 뜻

이 List를 가지고 아래 5가지의 경우를 구하면 된다

• minimum : 최소값
• maximun : 최대값
• mean : 평균
• median : 중앙값. List의 갯수가 홀수면 List의 가운데 값, 짝수면 List의 가운데값 2개의 평균
• mode : 빈도수가 가장 많은 값

여기까지 보고 별거 아니네하고 풀었다가 생각보다 고전했다...

함정은 바로 median이었는데 처음엔 값들의 중앙값으로 생각해서 [0,100,2,1]일때 값이 1,2,3뿐이니깐 중앙값을 2로 생각하고 접근했다

하지만 이 문제에서 원하는 중앙값은 index 에 대한 갯수들까지 고려해야하므로 [0,100,2,1]라면 1이 나와야한다

사실 테스트케이스를 생각하고 코드를 짰다면 아래처럼 안나오긴했을거 같은데 너무 또 덕지덕지 짜버렸다

내 정답은 아래와 같다

class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        minimum = -1
        maximum = -1
        mean = 0
        median = 0
        total_count = 0
        mode = (0, 0) # value, count
        
        for k, k_count in enumerate(count):
            if k_count == 0:
                continue
                
            if minimum == -1 or k < minimum:
                minimum = k
            if maximum == -1 or k > maximum:
                maximum = k
            mean = mean + k * k_count
            total_count = total_count + k_count
                
            if mode[1] < k_count:
                mode = (k, k_count)
            
        mean = mean / total_count
        
        middle = int(total_count / 2)
        is_odd = bool(total_count % 2 == 1)
        before_k = -1
        
        for k, k_count in enumerate(count):
            if k_count == 0:
                continue
            
            if is_odd:
                if middle == 0:
                    median = k
                    break
                if middle < 0:
                    median = before_k
                    break
            if not is_odd:
                if middle == 0:
                    median = (before_k + k) / 2
                    break
                if middle < 0:
                    median = before_k
                    break
            middle = middle - k_count
            before_k = k
        
        return [float(minimum), float(maximum), mean, median, mode[0] / 1]

그런데 처음엔 결과적으론 O(n)으로 끝나는 문제라서 속도는 상관없겠다란 생각에
메모리를 생각 안하고 중앙값 계산할때 아래처럼 무식하게 찾았다

results = []
for k, v in count:
    results.extends([k] * v)
m = int(results.length / 2)
if results.length % 2 == 1:
	median = results[m]
else:
    median = (results[m - 1] + results[m]) / 2

문제가 뭐냐면 count의 길이는 256으로 고정이지만 위의 방식을 따른다면
count 의 item의 value만큼 더 List의 크기가 늘어나기 때문에 메모리 문제가 발생한다

그래서 내가 생각한 방법은
위 코드에서 results의 index 중간값인 m(=middle)을 구하고
count를 돌면서 item의 value를 빼는 방식으로 구현했다

[0, 4, 3, 2, 2] 이라면 m = 5 이고
item의 index가 1일때 4를 빼서 m = 1
index가 2일때 3을 빼면 m = -2
=> 이때 2가 중앙값

다만 이 경우엔 케이스가 매우 많다는 문제가 있다

홀수인 경우, 
[0, 1, 3, 1] : 중앙값이 여러개인 경우(3 -> 2 -> -1)
[0, 1, 1, 1] : 중앙값이 1개인 경우(2 -> 1 -> 0)

짝수인 경우,
[0, 1, 2, 1] : 중앙값이 여러개인 경우(2 -> 1 -> -1)
[0, 2, 1, 1] : 중앙값이 1개인 경우(2 -> 0)

또 문제는 짝수인 경우는 index가 m-1, m인걸 따로 계산해야되는데
m-1이 이전 값일수도 있고 현재 값일 수도 있다
[0,1,1,1,1] : 중앙값은 (2+3)/2 = 2.5
[0,1,2,1] : 중앙값은 (2+2)/2 = 2

요것까지 고려해서 코드에 반영했더니...아름다운 if문 떡칠이 발생했다 ^^
뭐 직관적인게 좋은거니깐 + 정답이니깐 ㅎㅎ
(속도도 나름 상위권인듯?)