[python code review] 14주차 (세 용액, 도서관, 전시장)

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

2473번: 세 용액

[투포인터]

n = int(input())
lst = sorted(map(int, input().split()))
liquid = 4*(10**9)
answer = []

for i in range(n-1):
    start, end = i+1, n-1
    while start < end:
        total = lst[i] + lst[start] + lst[end]
        if abs(total) < abs(liquid):
            liquid = total
            answer = [lst[i], lst[start], lst[end]]

        if total < 0:
            start += 1
        elif total > 0:
            end -= 1
        else:
            print(lst[i], lst[start], lst[end])
            exit()

print(*sorted(answer))

 

[시간 초과 발생한 코드]

너무 아무 생각없이 dfs로 풀었고 시간 초과가 발생했다.

500C3에 대해 시간이 1초 정도 걸리는 걸 보니 500C3은... 안봐도 뻔한 결과였다. 

def dfs(arr, idx):
    global lst, n, answer, distance

    if len(arr) == 3:
        target = sum(arr)
        if abs(target - 0) < distance:
            distance = abs(target - 0)
            answer = arr[:]
        return
    for i in range(idx, n):
        arr.append(lst[i])
        dfs(arr, i+1)
        arr.pop()


answer, distance = [], 1e9
n = int(input())
lst = list(map(int, input().split()))
dfs([], 0)
print(*sorted(answer))

 

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

1461번: 도서관

[그리디]

음수와 양수로 나누어 별도로 리스트에 저장하여, m개씩 묶음을 지어서 묶음 중 가장 0으로부터 멀리 떨어진 수들만 d 리스트에 저장한다. ex) 5 8 11 25 31 처럼 값이 들어올 경우, m=2라면 31에 있는 책을 두면서 25에 위치한 책도 처리한다. 이런 식으로 동작하면 d = [31, 11, 5] 가 저장된다.   

마지막 한 번을 제외하고는 다시 제자리로 돌아와야 한다. 그래서 *2를 해주지만, 가장 마지막에 두는 경우 제자리에 돌아오지 않아도 되기에 2를 곱하지 않는다. 이때 제일 거리가 큰 31을 마지막에 꽂아둔다면 최소 걸음 수를 구할 수 있다.

n, m = map(int, input().split())
leftB, rightB = [], []
books = list(map(int, input().split()))

for book in books:
    if book < 0:
        leftB.append(book) # 음수 거리에 위치한 책들
    else:
        rightB.append(book) # 양수 거리에 위치한 책들
leftB.sort(reverse=True); rightB.sort() 
d = []
for i in range(len(leftB)-1, -1, -m): # m개씩 묶음지어 d 리스트에 저장
    d.append(-leftB[i])
for i in range(len(rightB)-1, -1, -m):# m개씩 묶음지어 d 리스트에 저장
    d.append(rightB[i])
d.sort()
answer = d.pop()
answer += sum(d)*2
print(answer)

 

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

2515번: 전시장

ㅇㅇ