99클럽 코테 스터디
무난한 문제였다.
1번 문제 Put Marbles in Bags : https://leetcode.com/problems/put-marbles-in-bags/description/
출처 : LeetCode
1번 문제 Put Marbles in Bags
풀이 접근
처음에 문제 조건을 착각하여 dp 문제로 접근했다(dp로는 시간복잡도상 아예 못 풀 것 같다).구간으로 자를 때 각 구간의 길이가 다 2 이상이어야 하는 줄 알았는데, 그렇지 않았던 것.
그래도 이 문제를 푸는 데는 한 가지 아이디어가 필요한데,
구간을 순서대로 나열했을 때, 앞 구간의 맨 뒤 원소와 뒤 구간의 맨 앞 원소는 인접한다.
즉, 인덱스를 기준으로 A~B, B+1~C, C+1~D, D+1~E 이런 식으로 나열된다는 것이다.
구하려는 값을 최대로 하든 최소로 하든 weight의 맨 앞과 맨 뒤 원소는 공통이므로, 그 사이는 B번째와 B+1번째, C번째와 C+1번째, D번째와 D+1번째 이런 식으로 인접한 두 원소씩의 합이 된다.
그리고, 구간의 길이가 1일 수 있으므로, B번째와 B+1번째를 골라도 B+1과 B+2를 또 고를 수 있다.
문제의 Example 1) weights = [1,3,5,1], k = 2
이 예시를 보면, 맨 앞과 맨 뒤의 1은 고정이므로, 최댓값과 최솟값의 차에는 영향을 안 준다. 따라서, 1+3, 3+5, 5+1 중 한 개(k-1개)를 고르는 문제가 되고, 최댓값 8(3+5), 최솟값 4(1+3)의 차인 4가 답이 된다.
전자의 경우는 [1,3],[5,1]로 자른 것이 되는 것이고, 후자는 [1],[3,5,1]로 자른 것이 된다. 두 경우 다, 쉼표를 기준으로 앞뒤로 인접한 두 원소의 합이 중요하다는 것을 알 수 있다.
k가 2보다 크면, 인접한 두 원소의 합 n-1개 (n은 weights의 length) 중 큰 값부터 k-1개의 합에서 작읍 값부터 k-1개의 합을 빼 주면 된다.
코드(Python3, Accepted, 최대 564ms, 30.37MB)
코드가 꽤 짧게 나온다. 다만 실행 시간은 그렇진 않은데, sum 안에 for문을 넣은 점이라던지 그런 게 비효율적이라 그런 것 같다.
pairs는 weight에서 인접한 두 원소의 합들이다.
class Solution:
def putMarbles(self, weights: List[int], k: int) -> int:
pairs = []
for i in range(len(weights)-1):
pairs.append(weights[i] + weights[i+1])
pairs.sort()
return sum(pairs[-1 - j] - pairs[j] for j in range(k-1))