📝 문제
준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.
준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.
🔒 제한사항
입력
첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.
출력
첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.
📚 입출력 예제
입력 1
5
1
2
1
2
1
출력 1
1
입력 2
6
1
2
1
2
1
2
출력 2
1
🤔 아이디어
- 파이썬 정렬 라이브러리의 시간복잡도는 최악의 경우에도 O(NlogN)을 보장
#1
일단 리스트로 입력
set으로 요소 1개씩 남기고
dict와 이용해서 개수 저장
-> 시간초과
#2
마지막에 value가 가장 큰 값 구하는 곳에서 시간초과 일어남
리스트 컴프리헨션을 이용하지 않고 lambda 함수를 이용하면 시간초과가 발생하지 않는다.
sorted(nums_dict.items(), key = lambda x:(-x[1],x[0]))
- 정렬의 key(기준이 되는 값)이 (-x[1], x[0])이다.
- 여기서 x[0]은 딕셔너리의 key, x[1]은 딕셔너리의 value를 의미
- 정렬은 기본적으로 오름차순인데 우리는 value를 기준으로 내림차순으로 정렬해야 하니까 첫 번째 기준이 -x[1]
- 최빈값이 많으면 작은 걸 출력하기 위해 두 번째 기준이 x[0], 즉 x[1]이 같으면 x[0] 순으로 정렬
🗝️ 풀이
import sys
n = int(sys.stdin.readline())
nums = []
for _ in range(n):
nums.append(int(sys.stdin.readline()))
nums.sort()
nums_dict = {}
nums_dict[nums[0]] = 1
tmp = nums[0]
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
tmp = nums[i]
nums_dict[tmp] = 1
else:
nums_dict[tmp] += 1
# nums_dict value 기준으로 sort
max_key = sorted(nums_dict.items(), key = lambda x:(-x[1],x[0]))
print(max_key[0][0]) # 빈도 수가 가장 큰 값이 여러 개면 최소값 출력
chick! chick!