난이도 : ●○○ | 풀이 시간 : 20분 | 메모리 제한 : 256MB | 기출 : 2019 SW 마에스트로 입력 테스트
문제
- 일직선상의 마을에 여러 집이 위치해 있다.
- 그 중 안테나로부터 모든 집까지의 거리의 총합이 최소가 되는 집에 안테나를 설치할 것이다.
- 안테나는 집이 있는 곳에만 설치할 수 있고 논리적으로 동일한 위치에 여러 개의 집이 존재할 수 있다.
입력조건
- 첫째 줄에 집의 수 N이 주어진다. (1<=N<=200,000)
- 둘째 줄에 N채의 집 위치가 공백으로 구분되어 1 이상 100,000 이하의 자연수로 주어진다.
출력조건
- 첫째 줄에 안테나를 설치할 위치를 출력한다.
- 안테나를 설치할 수 있는 위치가 여러 개일 경우 가장 작은 값을 출력한다.
입력예시
4
5 1 7 9
출력예시
5
아이디어
- 다른 모든 집까지 거리의 총합이 최소인 집 : 집 위치를 오름차순 정렬했을 때 중앙에 위치하는 집
- 단, 그런 집이 여러 개일 때는 가장 작은 값을 출력해야 한다.라는 조건을 잘 이해해야 한다.
- n이 홀수일 때는 중앙값이 단 하나이기 때문에
- data[n//2]가 유일한 답이 된다.
- n이 짝수일 때는 중앙값이 두 개인데, 그중 앞에 있는 것을 출력해야 하므로
- data[n//2]가 아니라 data[(n-1)//2]가 답이 된다.
코드
n = int(input())
data = list(map(int,input().split()))
data.sort()
print(data[(n-1)//2])
출처
이것이 취업을 위한 코딩테스트다 with 파이썬
'Algorithm > [이코테] 알고리즘 유형별 기출문제' 카테고리의 다른 글
[이코테] DFS/BFS 구현문제 - 인구 이동 python (0) | 2023.11.17 |
---|---|
[이코테] 정렬 문제 - 실패율 python (0) | 2023.11.05 |
[이코테] 정렬 문제 - 국영수 python (0) | 2023.11.04 |
[이코테] DFS/BFS 문제 - 경쟁적 전염 (1) | 2023.10.31 |
[이코테] DFS/BFS 문제 - 연구소 (0) | 2023.10.31 |