백준 & 프로그래머스

[백준] 1461번: 도서관 - python

hyukji 2023. 1. 10. 21:04

문제보기

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

 

1461번: 도서관

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책

www.acmicpc.net

 

 

 

 


 

풀이 및 코드

 

해당 문제는 Greedy문제로 solved.ac에 골드 5로 랭크되어 있다.

 

 

풀이법은 가장 먼 곳부터 생각하고 코드를 작성하면 편하다!(물론 실제로는 가장 먼 곳을 마지막에 가야 한다) 즉 가장 먼 곳으로 가되 그 다음으로 먼 책 m개를 챙겨서 가져간다고 생각하면 된다. 주의할 점은 실제로 가장 먼 곳은 갔다가 돌아오지 않앙 하기에 거리 * 2가 아닌 그냥 거리만 더해주면 된다. 또한 양수와 음수는 따로 계산한다. 이유는 양수 a와 음수 b를 같이 운반하고 0으로 돌아오면 이동 거리는 a+a + b+b가 된다. 이는 음수 양수 따로 운반한 a+a, b+b의 합과 같다! 

 

필자가 처음 코드를 짤 때에는 다음의 로직을 따라 작성했다.

  • input list를 정렬한 후에 음수, 양수로 나누어 0부터의 거리를 배열로 저장한다.
  • 거리가 가장 먼 위치를 찾아 answer에 더해주고, 해당 배열에서 m개를 제거한다.
  • 각각의 배열의 가장 큰 값 * 2를 answer에 더해주고, 해당 배열의 길이가 0이 될 때까지 m개를 제거한다

 

 

그런데 다른 분들의 코드를 보면서 더 좋은 코드가 있음을 알았다. 바로 해당 메서드를 이용한 코드이다.

arr = [1,2,3,4,5,6,7]
print(arr[::3])
# [1,4,7]

 

arr[a:b:c] 는 index a부터 index b까지 c개 단위로 꺼낸 list이다. 해당 메서드를 이용하면 다음과 같이 비교적 깔끔하게 코드를 짤 수 있다!

 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
loc = sorted(list(map(int, input().split())))
postive = []
negative = []
for l in loc:
if l < 0:
negative.append(-l)
else:
postive.append(l)
postive.reverse()
print((sum(negative[::m]) + sum(postive[::m])) * 2 - max(negative + postive))
view raw 1461.py hosted with ❤ by GitHub