[백준] No.1461 도서관 01

1461번: 도서관

2023 KAKAO 공채 2번 문제를 풀었었는데 그 문제와 굉장히 흡사하다.

이래서 문제를 많이 푸는 게 중요하다고 하는구나...를 느꼈다.

 

# ---------- Import ----------
from itertools import zip_longest as zip

# ---------- Function ----------
def toList(INPUT: list) -> list:
    return [i+1 for i, v in enumerate(INPUT) for _ in range(v)]    


def solution(cap, n, deliveries, pickups):
    result = 0
    
    d = toList(deliveries)[::-1][::cap]
    p = toList(pickups)[::-1][::cap]
        
    return 2 * sum([max(dv, pv) for dv, pv in zip(d, p, fillvalue=0)])

제출한 프로그래머스 코드이다. 문제 설명은 생략하고 간단하게만 설명한다.

toList() 함수는 배송하거나 회수할 목록을 list로 만들어주는 함수이다.

예를 들어서 [1, 3, 0, 2, 0]이라면 toList()를 거쳐 [1, 2, 2, 2, 4, 4]가 된다.

 

만약 한 번에 옮길 수 있는 용량이 2라면 [1, 2, 2, 2, 4, 4]에서 2개씩 자르면 된다.

이때 내림차순으로 정렬한 뒤 잘라야 한다. 가장 먼 곳부터 잘라야 가장 적게 움직일 테니.

우선 오름차순으로 생성한 배열은 뒤집고([::-1]), cap만큼씩 건너뛰며([::cap]) 잘라내면 [4, 2, 2]로 바뀐다. 

 

배송할 목록과 회수할 목록이 각각 [4, 2, 2], [5, 3, 1]이 되었다고 해보자.

배송이든 회수든 먼 거리가 있다면 그곳을 반드시 거쳐야 한다.

각 index를 비교하면서 더 큰 값을 다 더하면 되는 것이다. sum(max(dv, pv))에 해당한다.

이때 어느 한 쪽이 더 길어질 수 있으니 zip_longest를 사용하여 0으로 채우고 계산한다.

마지막으로 거리로 왔다갔다하기 때문에 마지막으로 2를 곱해주면, 식 완성이다.

 

여기서 2가지 아이디어를 가져왔다.

1. 가장 먼 곳부터 계산해야, 가장 적게 움직인다.

2. [::step]으로 계산할 거리를 잘라준다.

 

# ---------- Main ----------
positive = []
negative = []

length, limit = map(int, input().split())
books = list(map(int, input().split()))

for v in books:
    if v > 0: positive.append(v)
    else: negative.append(-v)

이번 백준 문제가 프로그래머스와 다른 가장 큰 점은 '숫자 범위'이다.

프로그래머스에서는 자연수만 주어지지만, 백준에서는 0을 제외한 정수가 주어진다.

그렇기에 따로 계산할 필요가 있다고 생각했고, positive와 negative로 나누었다.

 

negative는 이미 negative라는 list에 들어간 순간 음수라는 게 정해진다.

코드에서 필요한 것은 음수와 양수를 나누고, 각각에 대해 계산하는 것이다.

즉 나중에는 음수에서 부호를 뺀 '값'만이 필요하다. 그래서 negative에는 -1을 곱한 뒤 추가해 주었다.

 

# ---------- Main ----------
positive = sorted(positive, reverse=True)[::limit]
negative = sorted(negative, reverse=True)[::limit]

positive와 negative를 각각 내림차순 정렬을 진행하고, 최대 용량(limit)만큼 건너뛰며 자른다.

이때 [::-1]을 사용하여 역순 정렬하지 못하고, sorted()를 사용하여 정렬해줘야 한다.

프로그래머스와 다르게 기본 정렬이 되어있지 않은 상태이기 때문이다.

 

 

sort()가 아니라 sorted()를 사용한 이유는 sort()는 In-place 함수이기 때문이다.

sort()로 정렬하면 따로 [::limit]를 작성해줘야 하기에, 깔끔하게 한 줄로 작성하려고 sorted()를 사용했다.

 

# ---------- Main ----------
MAX = max(positive[0], negative[0])
print(2 * (sum(positive) + sum(negative)) - MAX)

이때 문제 조건에 "책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다"고 한다.

즉, 가장 먼 거리는 한 번만 더해주면 된다.

가장 먼 거리를 따로 더한 다음에, 이를 제외한다. 그리고 나머지를 전부 더하고 2를 곱한다.

이 과정이 깔끔하지 않다고 생각하여 조금 다르게 생각해보았다.

 

가장 먼 거리를 MAX라고 해보자.

코드에서 원하는 건 +MAX이다. 이는 2MAX - MAX이랑 똑같다.

모든 거리를 다 더하고 2를 곱한 다음, 마지막에 가장 먼 거리를 빼줘도 정답이 된다.

MAX는 positive[0]과 negative[0] 중에 하나이다. 정렬했기 때문에 0번째가 가장 크다.

 

# ---------- Main ----------
if not positive: MAX = negative[0]
elif not negative: MAX = positive[0]
else: MAX = max(positive[0], negative[0])

이때 조심해야 하는 점이 하나 있다.

양수가 하나도 없거나, 음수가 하나도 없을 수 있다는 것이다.

양수가 하나도 없다면(not positive), 자연스레 음수의 최댓값이 MAX이다.

음수가 하나도 없다면(not negative), 자연스레 양수의 최댓값이 MAX이다.

이런 조건문 없이 else만 작성한다면 IndexError를 겪을 지도 모른다.

 

골드 4라는 문제에 비해, 다행스럽게도 20분도 채 안 되어 한 번에 문제를 해결할 수 있었다.

확실히 비슷한 유형의 문제를 알고 있으면, 응용하여 다양하게 적용할 수 있는 것 같다.

그렇게 되기 위해서는 정말 많은 문제를 가리지 않고 풀어봐야 한다.

백준 문제만 푸는 것이 아니라, 실제 코딩 테스트 문제들도 종종 풀어봐야 겠다는 생각이 들었다.