[Algorithm] 백준 BOJ 2212 센서 python 파이썬 그리디 골드 5

Private 난이도 : ♥♥♥♡♡

2212번: 센서

import sys
n=int(sys.stdin.readline())
k=int(sys.stdin.readline())
sensor = list(map(int, sys.stdin.readline().split(' ')))
sensor = sorted(list(sensor))
print('정렬된 sensor', sensor)

if n <= k:
    print(0)
    exit()

length = []
for i in range(len(sensor) - 1):
    length.append(sensor[i + 1] - sensor[i])
print('센서 사이의 거리',length)  # [2, 3, 1, 2]
length.sort()
result=0

for i in range(k-1):
    length.remove(max(length))


print('수신 가능 영역의 최소 길이들 ', length)
print('수신 가능 영역의 최솟값',sum(length))

설명이 추가된 버전이다. 프린트는 지워야하고, 제출 버전은 링크에 있다.

설명

• 센서 사이의 길이를 구해서 가장 큰 것들을 기준으로 자른다는 아이디어
• 사실 while을 써서 max값들을 차례대로 remove하고 싶었는데 구현 못했다,, 그래서 그냥 for문을 써서 k-1개만큼 지웠다.
  • max를 지운다
    • for
      위의 코드
    • while
      구현 못함 -> 아쉬운 부분. 
      

      while len(length) != k +1 : 
          length.remove(max(length))

      아쉽게도 경우에 따라 이 알고리즘은 틀리게 된다.
  • min을 남긴다
    • while
      

      while len(length) +1!= k :
          result+=min(length)
          length.remove(min(length))

배운 점

• map
  list(map(int, f.readline().split(' ')))
  
  이런 map앞에 list를 씌워야 한다