[BOJ][2108번] 통계학

안녕하세요 Dibrary입니다.

이번에는 시간초과때문에 온갖 머리를 쥐어짰던 문제를 정리해보고자 합니다. 어휴 =_=;; (뭐 덕분에 Counter를 알게 되었으니까 다행이죠)

2108번: 통계학

 

---

문제는 간단합니다. 그저 평균, 중앙값, 최빈값, 범위 만 구하면 됩니다.

그 와중에 혹시라도 시간초과 걸릴까봐 (너무 쉬운거 같은 문제는 꼭 이런게 걸려있곤 해서 말이죠) 미리 아이디어를 좀 짰었습니다.

1. 값 받으면서 미리 정할 수 있는게 뭐 없을까?
2. 최대값, 최소값은 값을 받으면서 미리 확인해 나갈 수 있겠다.
3. 전체 갯수도 값 받으면서 미리 셀 수 있다.
4. 전체 값의 합도 값 받으면서 미리 셀 수 있겠다.

그래서 처음에 작성한 코드는 아래와 같습니다.

근데 백준에서 Numpy는 안되더라구요, 그 부분만 total_value / cnt로 수정했죠.

아니 근데 시간초과가?

이제 머리를 좀 써야 했습니다.

먼저 평균 계산에서는 이미 값을 받으면서 저장한 total_value와 cnt로 나누면 되므로 O(n)이 걸리지 않겠다고 판단했습니다.

그리고, 그 다음에 중앙값은 sort를 써야 했으므로, O(nlogn)이 걸리긴 하지만, 그렇다고 엄청 오래걸리는 것은 아니었습니다.

범주 역시 max_value - min_value만 하면 되었으므로 O(1)이었죠.

그럼 범인으로 예상되는 부분은 '최빈값'을 구하는 부분이었습니다. 

 

여기를 처음에는 dict( )로 담아서 계산하다가, 이 부분을 입력값 받으면서 dict자료형인 table에 담아버리고, 그 중에 max만을 뽑게 했었던 것입니다. 물론, 그럼에도 시간초과에 걸렸죠.

 

---

그래서 인터넷에 서치를 해 보니 Counter라는 기능이 있더라구요. 물론, Counter를 써도 통과할 지는 몰랐었습니다.

Counter는 아래 코드와 같이 '갯수'를 세 줍니다.

근데 저러면 Counter객체라서 결국 dict랑 뭐가 다른가... 이런 생각을 했었죠. 근데 Counter는 most_common메서드를 가지고 있다고 합니다. 해당 key-value꼴을 tuple로 묶어서 list로 만들어 주는 것이죠.

이걸 보면 문득 생각이 들지 않나요? (값, 갯수)라면, 갯수를 기준으로 정렬한 후에, 값이 작은것 중에 2번째인지만 확인하면 됩니다. 물론, 갯수가 가장 많은게 1개 뿐이라면 해당 값만 출력하면 되죠.

 

---

그래서 코드는 아래와 같습니다.

코드의 다른 부분은 거의 같습니다. 최빈값 구하는 부분만 Counter를 써서 구했죠.

Counter라는 기능이 있다는 것을 이번 문제를 풀어보면서 알게 되었습니다.