[정렬] 안테나

[ericagong]

⭐ 성찰

1. 무식하게! 무작정 문제 풀지 말고, (1) 시간 복잡도 예상하고 (2) 문제의 규칙성을 찾아 시간 복잡도를 어떻게 낮출 수 있을지 반드시 먼저 고민해야한다.
2. 길이가 짝수이든, 홀수이든 n = 길이, (n-1) // 2는 가운데 인덱스 보장(짝수인 경우는 왼쪽 가운데 인덱스)
   • 짝수인 경우 가운데 뒷 인덱스를 원하면 (n-1)//2 + 1.
3. python에서 min_v = math.inf, max_v = - math.inf 로 초기 세팅하자.
4. python의 abs() 함수는 파이썬 내장 라이브러리이기 때문에 바로 쓸 수 있다.
5. input = sys.stdin.readline을 써서 함수를 대체하여 인풋을 빨리 받아 시간 초과를 지양하라.

❓ 문제 상황

• 이코테 p.360
• 안테나

👨‍💻 문제 해결: 정렬

✅ 1차 풀이: 완전 탐색으로 인한 시간 초과

0. 집 위치 리스트 받음. 거리 리스트 생성.
1. for문으로 모든 집을 돌며, 다른 집과의 거리를 절대값 함수를 통해 계산해 거리 리스트에 추가.
2. 최소 거리를 구하고, 거리 리스트 for문을 돌며 최소값과 같은 거리의 집을 신규 리스트에 추가.
3. 신규 리스트를 오름차순 정렬한 뒤, 맨 앞의 가장 작은 값을 출력.

   
   import sys

input = sys.stdin.readline n = int(input()) li = list(map(int, input().split())) d = []

O(n^3): sum O(n), 리스트 이중 for 문 O(n^2) = (2*10^5)^3 = 8,000만

일반적인 코테 환경에서 python은 1초에 2,000만 연산 수행. >> 당연히 이 코드는 시간초과

for h in li: d.append(sum([abs(x - h) for x in li]))

min = min(d)

min_li = [] for i, dis in enumerate(d): if dis == min: min_li.append(li[i])

min_li.sort()

print(min_li[0])

### ✅ 2차 풀이: 규칙성을 찾아 정렬로 풀이
[[정렬]]
- 정렬 했을 때, 가운데에 위치한 집에 안테나를 설치해야 거리 최소값이 나올 것이라는 `💡 아이디어`를 도출해야함.
- 길이가 홀수인 경우, 무조건 가운데 인덱스 고르면 됨. 짝수인 경우, 앞의 인덱스를 고르든, 뒤의 인덱스를 고르든 차이 발생 X.
    - n = 길이, (n-1) // 2는 짝수든 홀수든 가운데 인덱스 보장(짝수인 경우는 가운데 앞 인덱스)
    - 짝수인 경우 가운데 뒷 인덱스를 원하면 (n-1)//2 + 1.
```python
import sys
input = sys.stdin.readline

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

li.sort()

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