[SWEA] 1204. 최빈수 구하기 (Python/D2)

SW Expert Academy

---

설명

1000명의 학생들 점수 중 최빈수(가장 많이 나타나는 값)를 출력해야 하는 문제이다.

다만, 최빈수가 여러 개 일 때에는 가장 큰 점수를 출력해야 한다.
각 테스트 케이스의 첫 줄에는 케이스의 번호가 주어지고, 그 다음줄부터는 점수가 주어진다.

 

풀이

1. 총 1000명을 탐색해야 하는데 데이터가 많아서 시간과 메모리를 줄이는 방법을 생각한다.

2. collections 모듈의 Counter 함수를 사용한다. counter 함수는 같은 값끼리 묶고 그 개수를 센다.

3. counter한 후 values 기준으로 내림차순 정렬을 한다.

4. 정렬한 리스트의 첫 번째 인덱스는 최댓값이 되기 때문에 첫 번째 key값을 출력한다.

 

• collection.Counter(list) - 같은 값끼리 묶어서 그 개수를 센다. 결과값은 dictionary 형태로 반환한다. 

• import collections를 할 경우 collections.Counter(list) 라고 작성해야 하고, from collections import Counter을 할 경우 collections을 작성하지 않고 사용할 수 있다.
• 결과값 예시 -  Counter({4: 4, 5: 2, 1: 1, 3: 1, 2: 1, 6: 1, 66: 1})

• sorted(Counter(list).items(), key=lambda pair:pair[i]) - 카운터 한 리스트도 정렬할 수 있다. 딕셔너리와는 조금 다른 형태이다.

• 리스트의 items를 가져와서 각 item의 key 혹은 value에 해당하는 값을 기준으로 정렬한다.
• i 자리에 0을 넣으면 key값을, 1을 넣으면 value값을 기준으로 정렬한다.
• 맨 뒤의 인자로 reverse=True를 넣으면 내림차순 정렬이 된다.

• 카운트 한 리스트[i][j] - i 자리에는 인덱스, j 자리에는 key값 혹은 value를 지정할 수 있다.

• count_score[0][1] 일 때, 첫 번째 인덱스의 value를 추출할 수 있다. 위의 결과값 예시에서 첫 번째 인덱스인 ({4: 4})에서 value값인 4가 출력된다.
• count_score[1][0] 일 때, 두 번째 인덱스의 key를 추출할 수 있다. 위의 결과값 예시에서 두 번째 인덱스인 ({5:2})에서 key값인 5가 출력된다.

 

Solution

from collections import Counter

t = int(input())
for _ in range(t):
    test_number = int(input())
    ans = 0
    count_score = []
    score = list(map(int, input().split())) 
    
    count_score = Counter(score) #리스트 값들을 카운트하고 저장한다.
    count_score = sorted(count_score.items(), key=lambda pair: pair[1], reverse=True) #value 기준으로 내림차순 정렬
    ans = count_score[0][0] #첫 번째 인덱스의 key값(점수)
    
    print("#"+str(test_number), ans)

 

다른 풀이(메모리와 시간 상에서 더 빠른 방법)

for i in range(1, int(input()) + 1):
    _ = input()
    score = list(map(int, input().split()))
    freq = [0] * 101  #0~100점까지의 빈도를 저장하기 위한 리스트
    ans = 0  #최빈수

    for grade in score:
        freq[grade] += 1 #현재점수의 빈도상승
        if freq[grade] >= freq[ans]: #현재점수의 빈도수가 최빈수보다 클 때
            ans = grade #현재 점수를 최빈수에 저장
    print(f"#{i} {ans}")

---

👩‍💻 회고

counter 함수를 사용하고 나서, '최빈수가 여러 개일 때 가장 큰 점수를 출력'해야 조건에 따라서 max 함수를 썼는데 key의 최댓값이 출력이 됐다. 빈도수 상관없이 원래 점수 리스트의 최댓값이 반환되는 문제가 있어서 values() 함수와 빈도수가 많은 요소 순대로 정렬되는 most_common() 메소드를 사용했다. 

그러나 이것도 내림차순으로 정렬이 안 돼서 sorted()를 사용해서 value 기준으로 내림차순 정렬이 되게 만들었다. 처음엔 sorted와 인자를 똑같이 사용했는데 사용하는 방법이 달라서 구글링해서 올바른 사용 방법을 알게 됐다.

 

1차, 2차 제출에 실패했었는데 1차 제출 때는 print에 테스트 케이스 번호를 출력하는 코드를 넣지 않았고, values를 사용하면 key값을 출력하지 못하는 문제 때문에 실패했다. 그래서 정렬한 후에 key값을 출력하도록 했다. 그러나 2차 제출에도 실패했는데 그 이유는 value기준으로 정렬해야 하는데 key 기준으로 정렬을 해버린 것이다. 다행히 문제점을 바로 찾게 돼서 3차만에 패스할 수 있었다.

 

패스하고 나서 다른 사람들의 풀이를 봤는데 라이브러리를 사용하지 않고도 풀 수 있는 방법이 있다는 것과 순수하게 구현하는 것이 시간복잡도, 공간복잡도 면에서 효율적이라는 것을 알게 됐다. 물론 파이썬의 취지와는 맞지 않지만 가끔은 복잡도도 고려하면서 구현을 해야겠다.