본문 바로가기

Algorithm/[이코테] 알고리즘 유형별 기출문제

[이코테] 정렬 문제 - 안테나 python

난이도 : ●○○ | 풀이 시간 : 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 파이썬