[이.취.코] [백준] Chap 14. 정렬 - Q24. 안테나

  • 0
  • 0
0
0

1. 📡 안테나

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😊 1차 시도 (성공 / 논리는 단순한데, 코드는 복잡함)

n = int(input())
array = list(map(int, input().split()))

if n == 1:
    print(array[0])
else:
    array.sort()

    if n % 2 == 0:
        half = n // 2 - 1
    elif n % 2 == 1:
        half = n // 2
    total = 1e9
    answer = half
    for i in range(half, half+2):
        temp_total = 0
        for j in range(n):
            temp_total += abs(array[i] - array[j])
        if temp_total < total:
            answer = i
            total = temp_total

    print(array[answer])

b. 😊 2차 시도 (나동빈님 코드 / 수학을 한다는건 이런거구나..)

n = int(input())

a = list(map(int, input().split()))

a.sort()

print(a[(n - 1) // 2])

a. 🙄 회고

내 풀이

  • 안테나로부터 모든 집까지의 거리의 총합이 최소가 되려면, 중앙에 있는 값을 찾으면 된다.

반성

  • 수학적으로 고민했다면, (n // 2) - 1이 아닌 (n - 1) // 2을 생각했을 것이다.

결론

  • 기본적인 수학은 코드를 획기적으로 줄일 수 있다..

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

집의 위치가 저장된 리스트의 인덱스는 0부터 n-1까지이다.


a. 1️⃣

n이 홀수일 때

홀수일 때는 단순히 중간값은 가운데에 있는 값이다.

n이 3이면 리스트의 인덱스는 아래와 같다.

0 1 2

중간값은 1이다.

n이 5이면 리스트의 인덱스는 아래와 같다.

0 1 2 3 4

중간값은 2이다.

n이 7이면 리스트의 인덱스는 아래와 같다.

0 1 2 3 4 5 6

중간값은 3이다.

즉, n이 홀수이면 (n-1)//2 혹은 n//2로 중간값을 구할 수 있다.


b. 2️⃣

n이 짝수일 때

중간값이 2개가 될 수 있다. 하지만, 문제에서 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다. 라고 명시되어 있기 때문에 2개의 값 중 작은 값을 출력한다.

n이 4이면 리스트의 인덱스는 아래와 같다.

0 1 2 3

중간값은 1이다.

n이 6이면 리스트의 인덱스는 아래와 같다.

0 1 2 3 4 5

중간값은 2이다.

n이 8이면 리스트의 인덱스는 아래와 같다.

0 1 2 3 4 5 6 7

중간값은 3이다.

즉, n이 짝수이면 (n-1)//2 혹은 (n//2)-1로 중간값을 구할 수 있다.

c. 결론

n이 짝수일 때와 홀수일 때 같은 공식으로 구할 수 있다면, 간단하게 문제를 풀 수 있다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

18310번: 안테나 (acmicpc.net). Baekjoon. (accessed Oct 2, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.