BOJ_1461 도서관

• TOC {:toc}

이 글은 백준 온라인 저지의 1461번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.14 (Python)

import sys
from bisect import bisect_left
input = sys.stdin.readline


def work(book):
    step = 0
    for i in range(0, len(book), M):
        step += abs(book[i]) * 2
    return step


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

idx = bisect_left(books, 0)
last = max(abs(books[0]), books[-1])
res = work(books[:idx]) + work(books[idx:][::-1]) - last

print(res)

아이디어 & 풀이

책이 0에 있기 때문에

양수 위치에서 음수 위치로 넘어갈 때는 0을 반드시 통과해야 하므로 양수 위치의 책과 음수 위치의 책을 동시에 정리하는 것은 의미가 없다.

• 입력받은 책 위치를 양수와 음수 부분을 나눠서 계산한다.

되도록 먼 곳에 있는 책을 한 번에 여러 권 갖다둬야 걸음 수를 최소화 할 수 있다. 예제 입력 1의 음수 부분을 예시로 봐보자.

• 위치: -39, -37, -29, -28, -6
• 가까이 있는 책 부터 2권씩 옮기면 걸음 수는 28 x 2 + 37 x 2 + 39로 총 169이다
  • (6, 28), (29, 37), 39
• 멀리 있는 책 부터 2권씩 옮기면 걸음 수는 6 x 2 + 29 x 2 + 39로 총 109이다.
  • (6), (28, 29), (37, 39)

마지막 책은 편도로만 가도 되기 때문에 가장 멀리 있는 책을 마지막으로 옮기는 것이 좋다.

• 양수 위치와 음수 위치 중 최댓값을 구해
• 전체를 왕복으로 반복했을 때 걸음 수에서 빼주면 된다.

디버그

• unBoundLocalError가 떴다.
  • 찾아보니까 변수 scope와 관련된 에러였다.
  • https://sikaleo.tistory.com/99
  • 함수 내에서 반복할 때 i를 따로 초기화를 하지 않고 range를 이용해서 사용한 후, 그 밖에서 다시 사용하려고 해서 에러가 난 것 같다.
  • 원래 i는 1단위로 순회하면서 인덱스에서 M을 곱해 더해야 하는 위치에 접근한 후, 마지막 남은 원소(e.g., 위 예시의 6 같은 경우)가 존재하면 따로 처리했는데 그냥 range의 step을 M으로 처리하는 방식으로 바꿔서 해결했다.
    • 덕분에 코드가 훨씬 깔끔해졌다.
• 양수 위치와 음수 위치를 각각 계산하기 위해 함수로 넘길 때 입력받은 리스트를 인덱스 노테이션을 이용해 범위를 지정해 넘겼는데 틀리는 경우가 생겼다.
  • 음수: books[:idx], 양수: books[N:idx - 1:-1] 였는데 이 경우 원소가 양수 한 개일 때 해당 원소를 포함하지 않는다.
  • 양수 리스트를 books[idx:][::-1]로 수정해서 해결했다.

피드백

• 두 번째 에러를 해결하는데 진행상 오류를 찾지 못해서 시간이 오래 걸렸다.
• 채점할 때 케이스 통과가 꽤 많이 진행되고 끊긴 것을 보니 극단적인 예제에서 틀린 것 같긴 했는데 해당 예시를 좀 더 빠르게 떠올리고 테스트했으면 좋았을 것 같다.

2022.04.06 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function getLen(arr) {
    const sorted = arr.sort((a, b) => b - a);

    const len = [];
    for (let i = 0; i < sorted.length; i += M) {
        len.push(sorted[i]);
    }

    if (len.length) {
        return [len.reduce((prev, curr) => prev + curr), len[0]];
    } else return [0, 0];
}

function main() {
    const pos = [];
    const neg = [];
    books.forEach((book) => {
        if (book < 0) neg.push(Math.abs(book));
        else pos.push(book);
    });

    const [posLen, posMax] = getLen(pos);
    const [negLen, negMax] = getLen(neg);

    return (posLen + negLen) * 2 - Math.max(posMax, negMax);
}

const [NM, lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));
const books = lines.split(" ").map((n) => parseInt(n));

console.log(main());

참고 답안

from heapq import heappush, heappop

N, M = map(int, input().split(' '))
books = list(map(int, input().split(' ')))
pos= []
neg= []
largest = max(max(books), - min(books))

for i in books:
    if i > 0:
        heappush(pos, -i)
    else:
        heappush(neg, i)

res= 0
while pos:
    res+= heappop(pos)
    for _ in range(M - 1):
        if pos:
            heappop(pos)
while neg:
    res+= heappop(neg)
    for _ in range(M - 1):
        if neg:
            heappop(neg)

print(-res* 2 - largest)

아이디어 & 풀이

sort 대신 최대 힙을 이용해서 구현했다.