성능 요약
메모리: 31120 KB, 시간: 32 ms
분류
그리디 알고리즘, 정렬
문제 설명
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.
입력
첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.
출력
첫째 줄에 정답을 출력한다.
00. 발상
-
마치 x축 수직선 상에서 주인공이 왔다 갔다 하면서 돌아오는 경로의 최솟값을 구하는 식으로 머릿속에 생각했다.
-
음수값과 양수값이 있으므로, 우선 리스트에 좌표값들을 전부 받은 뒤 이를 양수값에 해당하는 리스트와 음수값에 해당하는 리스트로 재분배 한다.
→ 한 번에 M권의 책을 들 수 있으므로, 반복문 안에서 M번씩 건너뛰며 결괏값을 계산한다.
(이 때, 상대적으로 거리가 먼 책을 가져갈 때 더 가까운 책을 같이 들고 가야하므로 배열을 내림차순으로 정렬해준다.) -
'마지막 책을 놓고나서는 0으로 돌아올 필요가 없다'는 조건이 있다.
→ 경로 상에서 가장 먼 거리의 값을 마지막 책으로 설정 해 한 번만 가게 만들어주면 되겠다.
01. 코드 작성
# 빠른 입력을 위해 stdin 사용
import sys
input = sys.stdin.readline
# 입력 처리
N,M = map(int,input().split())
books = list(map(int,input().split()))
positive = []
negative = []
last = 0
# books 리스트에서 양수값, 음수값을 각각 리스트로 분할
# 절대값이 가장 큰 값을 last 변수로 할당
for book in books:
last = max(abs(book),last)
if book > 0:
positive.append(book)
elif book < 0:
negative.append(book*-1)
# 각 리스트를 내림차순 정렬
positive.sort(reverse=True)
negative.sort(reverse=True)
# M칸 씩 건너뛰면서 값을 2번씩 더함
result = 0
for i in range(0,len(positive),M):
result += positive[i]*2
for i in range(0,len(negative),M):
result += negative[i]*2
# result에서 last값 빼줌
result -= last
# 결과 출력
print(result)02. 느낀 점 및 회고
-
사실, 오늘은 문제를 자력으로 해결하지 못했다.
발상하는 부분에서 '리스트를 두 개로 나누어 계산한다'는 생각을 하지 못했다. -
계속해서 시간을 쓰기에는 낭비라고 생각해, 솔루션을 찾아보고 이를 이해한 뒤 혼자 다시 코드를 짜보는 식으로 학습했다.
발상적인 부분만 해결하면, 코드 로직이 어렵지는 않았다. -
Greedy나 DFS 등 발상적인 부분이 중요한 문제가 출제 되었을 때, 나의 약점이 여실히 느껴진다. 이를 보완하기 위해 부단히 노력해야겠다.
++ 얼마 전에 풀었던 BFS 문제(백준 4485번)도 복습하였다.
문제를 한 번 풀고 넘어가서 까먹기 보다는, 해당 알고리즘에 대해 복습하면서 다음에도 적용할 수 있도록 익숙해지는 것이 중요한 것 같다.
#99클럽 #TIL #개발자취업 #코딩테스트준비 #항해99
