BOJ 1461 : 도서관 (Python)

 

문제

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

1461번: 도서관

 

 

코드

풀이의 논리는 맞으나 틀린 코드이다. 틀린 이유와 정답 코드는 가장 아래에서 !

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().split())
init = list(map(int,sys.stdin.readline().split()))

init.sort()
array = deque(init)

count = 0
pivot = -1
diff = max(abs(array[0]),abs(array[len(array)-1]))

for i in range(len(array)-1):
    if array[i]<0 and array[i+1]>0:
        pivot = i
        break
        
i = len(array)-1
    
while i > pivot:
    count += abs(array[len(array)-1]) * 2
    for j in range(k):
        i -= 1
        array.pop()
        if i<=pivot:
            break
i = 0

while i <= pivot:
    count += abs(array[0]) * 2
    
    for j in range(k):
        i += 1
        array.popleft()
        if i > pivot:
            break
print(count-diff)

 

 

풀이

 

init 리스트에 책 위치 값을 넣어서 sort 한다. 그리고  init 리스트를 deque 로 변환한 것이 array이다.

→ pop()과 popleft()를 이용하기 위해서

 

※ 굳이 popleft()를 쓰기 위해 deque으로 변환하기 보다는 음수, 양수 리스트를 나누어서 양수는 sort를 reverse로 하면 더 이해하기 쉬울 것 같다.

 

# pivot = -1 (pivot 초기값은 -1로 설정)

for i in range(len(array)-1):
    if array[i]<0 and array[i+1]>0:
        pivot = i
        break

음수와 양수를 구분하기 위해서 pivot 값을 설정한다.

예를 들어 리스트에 -5 -4 -3 6 7 이 있으면 pivot은 2(-3이 있는 인덱스)가 된다. → 앞 숫자의 인덱스를 기준으로 함

 

diff = max(abs(array[0]),abs(array[len(array)-1]))

가장 멀리 있는 책은 왕복하면 손해이므로 마지막에 정리하고 끝내는 것이 이득이다.

그래서 초기에 diff 변수에 array 중에서 절댓값이 가장 큰 값을 저장해둔다. 

array는 정렬이 돼 있는 상태이므로 가장 왼쪽의 절댓값과 가장 오른쪽의 절댓값만 비교를 하면 된다.

 

i = len(array)-1
    
while i > pivot:
    count += abs(array[len(array)-1]) * 2
    for j in range(k):
        i -= 1
        array.pop()
        if i<=pivot:
            break

먼저 pivot의 오른쪽에 있는 영역부터 시작한다. (양수 영역)

가장 오른쪽에서부터 왼쪽으로 진행된다.

count 에 해당 인덱스에 있는 원소의 절댓값을 저장한 후 for문을 이용해 세준이가 들 수 있는 책 권수만큼의 원소를 패스한다.

→ 더 멀리 있는 책을 꽂아두고 원점으로 돌아오는 길에 함께 들고 온 책들을 정리하면서 올 수 있기 때문이다.

 

 

pivot의 왼쪽에 있는 영역도 마찬가지로 진행한다. (음수 영역)

이번에는 가장 왼쪽에서부터 오른쪽으로 진행한다. → 절댓값이 큰 순서대로임

 

 

위 코드가 틀린 이유와 정답 코드

import sys
from collections import deque
n, k = map(int,sys.stdin.readline().split())

init = list(map(int,sys.stdin.readline().split()))
init.sort()
array = deque(init)

count = 0
pivot = -1
diff = max(abs(array[0]),abs(array[len(array)-1]))

for i in range(len(array)-1):
    if array[i]<0 and array[i+1]>0:
        pivot = i
        break


i = len(array)-1

#아래의 if문을 넣어줘야 오류 발생 X
if pivot== -1 and array[0] < 0:
    pivot = len(array)-1
    
while i > pivot:
    count += abs(array[len(array)-1]) * 2
    for j in range(k):
        i -= 1
        array.pop()
        if i<=pivot:
            break

i = 0

while i <= pivot:
    count += abs(array[0]) * 2
        
    for j in range(k):
        i += 1
        array.popleft()
        if i > pivot:
            break

print(count-diff)

 전체 숫자가 음수인 경우에서 원래 코드라면 pivot은 -1로 그대로 남아있어서 while i > pivot 을 거쳐야하는데 이 while문은 원래 양수 위치들을 위한 것이므로 오른쪽에서 왼쪽으로 진행한다. 이에 반해 음수들은 왼쪽에서 오른쪽으로 진행해야하므로 오류가 발생한 것이다.

 그래서 pivot 이 -1 이고 array의 첫 원소가 음수라면 (== 책의 위치가 모두 음수라면) pivot을 len(array)-1 로 변경해서 첫번째 while문을 거치지 않고 아래의 while문에서 진행할 수 있도록 한다.