안테나(p.360) - 정렬 문제(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명

 

일직선상의 마을에 여러 채의 집이 위치해 있습니다. 이 중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했습니다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록 설치하려고 합니다. 이때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능합니다. 

 

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하세요. 

 

예를 들어 N = 4이고, 각 위치가 1, 5, 7, 9일 때를 가정하겠습니다. 

 

N = 4, 위치 1, 5, 7, 9일때

 

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총합이 (4 + 0 + 2 + 4) = 10으로, 최소가 됩니다. 

 

 

입력 조건

 

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

 

출력 조건

 

• 첫째 줄에 안테나를 설치할 위치의 값을 출력합니다. 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력합니다. 

 

입력 예시 

 

4
5 1 7 9

 

출력 예시

 

5

 

 

---

 

문제 해설

 

필자가 문제를 볼 때마다 잘못 읽는 문제다. 안테나를 설치할 위치를 출력해야 하는데, 무의식적으로 안테나 위치와 집까지 거리의 총합의 최솟값을 출력하는 거라고 착각한다. 문제 설명 부분만 빠르게 읽고, 출력 조건을 꼼꼼하게 읽지 않은 게 원인인 것 같다. 

 

책에서 제시하는 해설에서는 중간값에 안테나를 설치하는것이 가장 최소거리가 된다고 한다. 그래서 코드도 정렬 후 1줄로 끝난다. 다른 방법도 있을 것이다. 여러 줄의 코드를 이용해서 작성하는 방법이 있을 거다. 하지만 이런 유의 문제는 간단한 1줄로 공식을 유추해서 푸는 문제다. 예전에도 비슷한 문제를 풀어봤는데, 제한시간을 0.15초로 하는 문제들은 반복문을 돌리지 말고 이렇게 공식을 유추해서 풀어야만 했다. 다음엔 비슷한 문제를 만나면 처음부터 반복문 돌릴 생각을 하지 말고 일정한 패턴이 보이는지를 생각해봐야겠다. 이제 해설을 보겠다. 

 

책에서 제공하는 해설 코드는 다음과 같다. 

 

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

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

 

정말 간단하다. 문제의 출제자가 원하는게 이렇게 풀라고 하는 것일 것이다. 

 

입력받고 정렬하고 중간값을 정렬하면 끝. 

 

새로이 해설을 추가할 내용이 없다. 그래서 필자가 처음에 생가간 반복문 돌리는 방법도 올려보겠다. 

 

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

temp = 1e9 
result = 0 

for home in array: # 안테나는 집이 위치한 곳에만 설치할 수 있으므로 
  sum = 0
  for target in array: # 안테나 설치한 기준위치 
    sum += abs(home - target) 
  if sum < temp: 
    temp = sum
    result = home # 현재값이 최소값이니 저장 
print(result)

 

입력 예시 2

 

6
1 2 3 5 8 9

 

출력 예시 2

 

3 # 설치할 위치를 의미

 

문제 설명에 있는 입력 예시와 지금 적은 입력 예시 2에서는 올바르게 작동하는 걸 확인한 코드다. 하지만, 백준에서 실행해본 결과 시간 초과 판정이 나오니 출제자가 의도한 방향과 다르다고 할 수 있다. 

 

'시간 초과' 판정이 나온다.

 

시간 복잡도가 O(N²)여서 통과를 못한 것 같다.

 

이 문제를 풀면서 시간제한이 1초여도 충분하지 않을 수 있다는 걸 느낄 수 있었다. 

 

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

18310번: 안테나