[CodeUp/2021] 산도 측정 (Python)

Problem : 산도 측정 (codeup.kr)

Status : Solved

Time : 00:21:47

 

---

 

문제 설명

 

당신은 강의 상태를 결정하기 위해 매우 긴 강에서 산도 레벨 수치를 수집하고 있습니다.

강에는 N(2 ≤ N ≤ 2 000 000)개의 센서가 있고, 각 센서는 정수 수치 R(1 ≤ R ≤ 1 000)을 사용합니다.

당신은 연구의 목적으로 각 수치의 빈도를 알고 싶어합니다. 그리고 두개의 빈도가 가장 높은 수치 사이의 절대 차를 구하려고 합니다.

만약 가장 빈도가 높은 수치가 두개 이상이면, 그 차이 계산이 빈도가 높은 두 수치의 최대 절대 차이어야 합니다.

보충 설명)

예를 들어, 센서의 개수가 5개이고, 1 1 1 4 3 이라면

빈도가 가장 높은 센서는 1이고(3회), 두 번째로 높은 빈도는 4와 3인데 빈도 수치의 최대 절대 차가 되려면 4를 선택해야 한다.

따라서 4 - 1 = 3 이된다.

 한마디로 빈도가 높은 두 센서를 찾아서 차를 구하되 차이가 최대가 되게 하는 문제입니다.

 

입력 및 출력

 

입력

첫째 줄에 센서의 개수 N이 입력된다. ( 2 <= N <= 2,000,000)

둘째 줄부터 N+1의 센서의 산도 수치 R(1 <= R <= 1,000)이 차례로 입력된다.

 

출력

위에서 설명한대로 두개의 가장 빈도가 높은 수치의 절대차를 정수로 출력하시오.

 

입력 예시

5

1

1

1

4

3

 

출력 예시

3

 

---

 

풀이

 

요즘 취업용 코테에서 나오는 문제들이 요구하는 문해력 및 수리능력 수준이 높아졌다는게 느껴진다. 이 문제는 그런 문해력, 문제에 대한 이해를 요구하는 문제라 쉬운 난도에도 불구하고 가져왔다.

 

사실 산도 입력은 모두 어떤 방식으로 카운팅을 하면 되고, 그것을 카운트한 빈도수를 기준으로 정렬하면 기본적인 세팅은 끝난다. 문제는 그 다음. 두 개의 가장 빈도가 높은 수치의 절대차를 정수로 출력하시오 가 되겠다. 이 문장에 대한 해석 때문에 정답률이 난이도에 비해 낮게 나오지 않았나 싶다.

 

두 개의 가장 빈도가 높은 수치는 다음과 같은 경우가 성립한다 :

1. 공동 1위 빈도(1위 빈도의 수치가 둘 이상일때)

-  이 경우는 1위 빈도를 가진 숫자의 최대값과 최소값의 차가 정답이 된다.

2. 빈도 수치가 단 하나일때

- 모든 입력이 같은 수치일 때 발생한다. 0을 출력한다.

3. 2위 빈도가 존재할때

-이 경우는 1번 케이스에 해당하지 않으면서 2위 빈도가 하나 이상 존재할때를 의미한다. 1위 빈도는 무조건 하나이므로(아니라면 1번 케이스에서 걸러진다), 1번 케이스와 2위 빈도 케이스를 전부 비교하며 그 중 절대값 차가 최대인 값을 저장하면 된다.

 

풀이 코드

from collections import defaultdict
import sys

input = sys.stdin.readline

N = int(input())
freq_dict = defaultdict(int)

for _ in range(N) :
  freq_dict[int(input())] += 1

freq_list = sorted([(key, val) for key, val in freq_dict.items()], key = lambda x : (-x[1], x[0]))

cnt = 0
f_min = f_max = freq_list[0][0]
f_val = freq_list[0][1]

for num, freq in freq_list :
  if cnt == 1 :
    if s_val > freq :
      break
    s_max = max(s_max, abs(f_max - num))

  else :
    if f_val > freq :
      s_max = abs(f_max - num)
      s_val = freq
      cnt += 1
      continue
    f_min = min(f_min, num)
    f_max = max(f_max, num)

if f_min != f_max :
  print(f_max - f_min)
else :
  if s_val > -float('inf') :
    print(s_max)
  else :
    print(0)