[백준] 18310번 안테나(Python - 파이썬)

백준 18310번 문제입니다. (solved.ad)기준 실버 3 문제입니다.

https://www.acmicpc.net/problem/18310

18310번: 안테나

첫째 줄에 집의 수 N이 자연수(1<= N <= 200,000)로 둘째 줄에 N채의 집의 위치가 공백을 기준으로 자연수로 주어집니다.(1 이상 100,000)이하

 처음에 문제를 보고 아무생각없이 2중 반복문을 사용하여 집 하나하나를 비교해서 갑을 도출하려고 하니 시간 초과 오류가 났습니다. 생각을 조금 해보니 오름차순으로 정렬을 하고중간만 비교하면 정답이 나올 것이라는 판단이 들어 다시 코드를 작성하여 보았습니다.

 아래 코드에 작성되어있는 주석은 예제 입력 1을 기준으로 작성하였습니다.

import sys
n = int(sys.stdin.readline().rstrip()) # 4 입력
home = list(map(int, sys.stdin.readline().rstrip().split())) # [5, 1, 7, 9] 입력
home.sort() # [1, 5, 7, 9] / 오름차순으로 정렬
first = True # 첫번째 반복문인지 판별

middle = len(home) // 2 # 2

# home리스트의 1 ~ 2 인덱스만 확인함.
for i in range(middle-1, middle+1) :
    # 다음 비교를 위해 0으로 초기화
    length = 0
    for j in home :
        # 비교할 집(home의 중간인덱스) - home의 모든 원소
        # 길이를 구하는 것이기 때문에 절댓값을 사용하여 length에 더해줌
        length += abs(home[i]-j)

    if first == True: # 첫번째 반복문이 참이라면
        # first를 False로 바꿔주어 다음부터
        # 이 조건문이 실행되지 않도록 함.
        first = False
        # 첫번째 비교이기 때문에
        # 최소 길이를 담을 변수인 min_length에 length 값을 넣어줌
        min_length = length
        # 정답에 집의 위치를 넣어줌
        ans = home[i]

    else :
        # min_length보다 방금 구한 집의 위치에서
        # 길이가 더 작다면
        if (length < min_length) :
            min_length = length
            ans = home[i]

print(ans)

 위의 코드가 제가 문제를 풀어낸 코드입니다. 풀고나서 책에 있는 정답코드를 보니 굉장히 간단하게 풀 수 있는 문제였습니다. 저는 중간값 언저리에 정답조건을 만족하는 값이 있을 줄 알고 비교를 하도록 코드를 작성하였는데 그냥 중간값을 출력하면 되는 문제였습니다.

 예시로 집의 위치가 1, 2, 3, 5, 8, 9라고 가정을 하면 3/5에 안테나를 설치하였을 때 거리의 총합이 2+1+2+5+6 = 16으로 최솟값이 됩니다. 하지만 중간에서 벗어난 2에 안테나를 설치하게 된다면 1+1+3+6+7 = 18로 거리가 더 증가하게 됩니다. 따라서 이 문제는 집의 위치를 입력 받아 정렬하고 중간값을 출려하면 되는 문제입니다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

# 중간값(median)을 출력
print(data[(n-1) // 2])

 위의 코드가 이것이 코딩테스트다(이코테)에 있는 정답 코드입니다... 매우 간결하죠?...