[BOJ] 2548. 대표자연수(python)

브루트포스(brute force): 전체탐색 가능한 모든 경우의 수 전체탐색

1차시도

for j in l:
	cnt = abs(i-j)
	cnt += cnt

cnt를 두 번씩 저장하는 꼴이 되어 출력값이 이상해짐

for i in range(1, N+1):
  cnt = 0
  sum= 0
  for j in l:
	cnt = abs(i - j)
	sum +=cnt

다음과 같이 sum을 이용해 값을 저장하였어야했음

2차시도

N = int(input()) #6 
l = list(map(int,input().split())) #4 3 2 2 9 10
min = int(1e9)

for i in range(1, N+1):
  sum= 0
  for j in l:
    sum += abs(i - j)

  if sum < min:
    min = sum
    ans = i

print(ans)

시간초과: 전체탐색 하면 그럴 수 밖에 없음

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

import sys
input = sys.stdin.readline

여러 줄을 입력 받아야하는 경우 input보다 sys.stdin.readline 사용할 경우 시간단축 가능

→ 근데도 시간 초과 뜸

3차시도

중앙값을 이용하여 푸는 문제

주어진 값들을 오름차순으로 정렬했을 때 가장 중앙에 위치하는 값

대표자연수 i 가 커질 때 마다 오른쪽에 있는 수들과의 거리가 1씩 감소하며, 왼쪽에 있는 수들과 거리가 1씩 증가

전체 값을 정렬하고 중앙값이 곧 대표 자연수

만약 N이 홀수 개라면 중앙값이 1개이지만, 짝수 개라면 중앙값 2개 → 둘 중 작은 수 고르면 됨

N = int(input())
l = list(map(int,input().split()))
l.sort()

if N%2 == 0: # N이 짝수인 경우
  num = l[N//2 - 1] # list index 0부터 시작
else:
  num= l[N//2]
print(num)

📍sort함수

sort함수의 경우 return 값이 존재하기 않고 list 자체를 변경해줌
print(list.sort())로 바로 출력 한다면 none이 나오게 됨

즉, l= list(map(int, input().split())).sort() 처럼 정렬 후 변수에 저장하면 안됨.