-
2108. [Python]통계학Python_알고리즘/Silver III 2023. 2. 25. 00:14
1. 문제
https://www.acmicpc.net/problem/2108
2108번: 통계학
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 256MB
- 구현
- 정렬
3. 파이썬 코드
import sys input = sys.stdin.readline N = int(input()) # sys.maxsize 사용할 경우 python 에서 낼 수 있는 최대값을 불러올 수 있다고 한다. min_value = sys.maxsize max_value = -sys.maxsize # 모든 값들을 더해줄 변수 total = 0 # 들어온 숫자 딕셔너리로 몇개 들어왔는지 카운트 num_dict = {} # 들어온 숫자들 리스트 check_list = [] # 최빈값 구하기 위한 리스트 num_list = [] for _ in range(N): num = int(input()) # 들어온 값이 max_value 와 비교해서 크면 값을 덮어 씌움 if max_value < num: max_value = num # 똑같이 min_value 와 비교해서 작으면 덮어 씌움 if min_value > num: min_value = num # 들어온 값을 더해줌 total += num # 딕셔너리안에 있으면 value 값을 +1 없으면 추가 if num in num_dict: num_dict[num] += 1 else: num_dict[num] = 1 # 숫자들 리스트에 저장 check_list.append(num) # 숫자들 정렬 check_list.sort() # 딕셔너리 value 값중 최빈값 저장 max_count = max(num_dict.values()) # 딕셔너리를 순회하며 value 값이 1이 아니면서 max_count 랑 같은경우 최빈값 리스트에 값저장 for k,v in num_dict.items(): if v == max_count and v != 1: num_list.append(k) # python round는 오사오입을 적용하지만 앞자리가 홀수냐 짝수냐에 따라서 결과가 달라진다. # 앞의 자리가 짝수인지 홀수인지 체크해주는 변수 생성 check_avg = total/N # 앞자리가 짝수인 경우 홀수로 만들어서 반올림한 후 +1 if (check_avg//1)%2 ==0: check_avg = round(check_avg-1)+1 else: check_avg = round(check_avg) # 최빈값이 2개이상인 경우 num_list를 정렬한 후 2번째 값 출력 if len(num_list) > 1: num_list.sort() print(check_avg) print(check_list[N//2]) print(num_list[1]) print(max_value-min_value) else: print(check_avg) print(check_list[N//2]) # num_list 값이 0 인 경우 if len(num_list) == 0: # N 이 1이 아니면 check_list에서 2번째 값을 출력 => 문제에서 요구한 것 if N != 1: print(check_list[1]) # 그 외의 경우 0이나 -1 출력 같기때문 else: print(check_list[-1]) # num_list 길이가 1인 경우 0번째 인덱스 출력 else: print(num_list[0]) print(max_value-min_value)
4. 문제를 풀고난 후 생각
- 처음 코드를 구현했을 때 예제는 다 잘돌아가서 제출을 했지만 1, 2 %로 넘어가서 바로 틀렸다.
- 여러 반례들을 찾아보고 적용해봤지만 틀린 부분을 짐작할 수 없었다.
- 고민하다가 python round가 앞자리가 홀수인지 짝수인지에 따라서 반올림이 다르게 적용되는 것이 생각나서 혹시나 해서 고쳤다.
- 이 부분을 고치고 난 후 최대값 최소값도 sys.maxsize를 통해서 구현을 한 후 제출하니 답이 맞았다.
- 시간초과를 생각해서 탐색과 정렬을 최소한으로 줄여볼려고 스스로 생각해서 짠 코드다보니 뭔가 길이가 길고 좀 지저분해보였지만 아직 내 실력으로는 여기까지가 최선인 것 같다.
5. 문제를 푸는데 도움이 되는 지식
- 정렬
- sys.maxsize
- 딕셔너리
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1515. [Python]수 이어 쓰기 (0) 2023.04.14 14425. [Python]문자열 집합 (0) 2023.03.01 1463. [Python]1로 만들기 (0) 2023.02.11 2579. [Python]계단 오르기 (0) 2023.02.06 17413. [Python]단어 뒤집기 2 (0) 2023.02.05