국영수

문제 Acmicpc

Solution

1
2
3
n=int(input())
house=sorted(list(map(int, input().split())))
print(house[(n-1)//2]) # n-1인 이유는 짝수일때 중간값은 2개인데 작은 값을 출력하라고 했기때문

처음 이 문제를 보고 1부터 n까지 각 요소에 대한 차이의 합을 계산해서 최소가 되는 인덱스를 반환하면 되지 않을까 했다.

(틀린 코드)

1
2
3
4
5
6
7
8
9
10
n=int(input())
house=sorted(list(map(int, input().split())))
min_=200001
loc=0
for i in range(1,n):
    dist=sum(map(lambda x:x-i,house))
    if dist<min_:
        min_=dist
        loc=i
print(loc)

당연히 시간 초과가 났다. 처음 작성한 코드는 시간복잡도가 O(N^2)이고 주어진 자연수의 범위가 20만까지이므로 20만의 제곱이 된다.

문제를 잘못 읽었었다. 나는 1,5,7,9가 주어질 때 1에서 9까지의 모든 정수부를 계산했는데, 다시 보니 주어진 값에서만 안테나를 설치할 위치를 고를 수 있었다.

주어진 리스트를 오름차순으로 정렬하고 중간 값을 반환하면 최적의 위치가 된다. 짝수일 경우 중간값이 2개가 되는데, 문제를 보면 여러 값일 경우 가장 작은 값을 출력하라고 했기 때문에 중간에 있는 인덱스를 계산할 때 n이 아닌 n-1로 생각하면 된다.