[백준] 1461번 : 도서관

1461번: 도서관

1461번: 도서관

🤔 문제분석

가장 큰 수는 마지막에 돌아가지 않아야함으로, 제일 마지막에 방문한다. 제일 작은수부터 쌍으로 방문해나아간다. 거리에는 마이너스 값과 플러스값이 있는데 둘이 구분을 해주어야한다. 마이너스 위치에서 플러스 위치로가려면 0을 지나가야하기때문에 구분해서 문제를 풀어도 상관이 없다.

저는 마이너스와 플러스를 구분하여 배열을 생성하였고, 마지막에 도착지점으로부터 첫번째 도착지점까지를 거꾸로 순회하게 문제를 해결하였습니다.

• search 함수는 마이너스쪽을 탐색할지, 오른쪽을 탐색할지, 탐색이 끝났는지에 대한 조건 함수이다.
• pop_value 함수는 해당 위치에서 가장 먼 거리에있는 값 M개를 pop하여 거리를 리턴해주는 함수이다.

제 코드에서 중요한점은 처음 뽑은 데이터는 가장 나중에 놓일 책임으로 가중치를 그냥 더한다. 그렇지 않은경우는 책을 두고 다시 돌아와야 하는경우임으로 곱하기 2를 하여 더하였다.

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

NONE = -1
PLUS = 0
MINUS = 1

books = list(map(int, input().split()))
plus_books = []
minus_books = []

for book in books:
    if book > 0:
        plus_books.append(book)
    else:
        minus_books.append(abs(book))

plus_books.sort()
minus_books.sort()

def search():
    plus_value = 0
    minus_value = 0
    if plus_books:
        plus_value = abs(plus_books[-1])
    if minus_books:
        minus_value = abs(minus_books[-1])
        
    if plus_value == 0 and minus_value == 0:
        return NONE
    elif plus_value > minus_value:
        return PLUS
    else:
        return MINUS
    
def pop_value(arr : list):
    cnt = M
    max_value = 0
    while arr and cnt > 0:
        max_value = max(max_value, arr.pop())
        cnt -= 1
        
    return max_value

first_flag = True
ans = 0
while True:
    target = search()
    
    if target == NONE:
        break
    
    value = 0
    if target == PLUS:
        value = pop_value(plus_books)
    else:
        value = pop_value(minus_books)
    
    if first_flag == True:
        ans += value
        first_flag = False
    else:
        ans += value*2

print(ans)

🎯 피드백 및 개선사항

리스트의 성질을 이용하여 문제를 예쁘게 풀으신분이 있어서 참고하여 가져왔습니다.

result값에 더하는데 튜플형식으로 추가한다. 가장 큰 값을 기준으로 M개를 선택하여 튜플에 추가하게되고, result값을 가장 작은 순으로 정렬한뒤 마지막 원소전까지 2를 곱하여 더하고, 마지막원소는 그냥 더한다.

N, M = map(int, input().split())
books = list(map(int, input().split()))

plus_books, minus_books = [], []
for book in books:
    if book < 0:
        minus_books.append(book)
    else:
        plus_books.append(book)

plus_books.sort(reverse=True)
minus_books.sort()

result = []
for i in range(0, len(plus_books), M):
    result.append(tuple(plus_books[i:i + M]))

for i in range(0, len(minus_books), M):
    result.append(tuple(minus_books[i:i + M]))

result.sort(key= lambda x: abs(x[0]))

ans = 0
for i in result[:len(result) - 1]:
    ans += abs(i[0]) * 2

ans += abs(result[-1][0])

print(ans)