Leetcode - 368. Largest Divisible Subset

문제 개요

중복이 없는 양의 정수 배열 nums가 주어졌을 때, 아래의 조건을 만족하는 제일 큰 부분 집합을 구하라

subset의 index i 및 j가 주어졌을 때
1. answer[i] % answer[j] == 0 또는
2. answer[j] % answer[i] == 0 

예시

nums = [1,2,4,3] 이면, answer = [1,2,4]

1 % 2은 1이지만 2 % 1 = 0 을 만족하기 때문

문제 분석

각 nums는 중복이 없지만, 정렬되어 있지 않다. 즉 nums를 정렬한 후 접근한다.

nums중 필수로 들어갈 수 있는 item은 1로 분석된다. 1과 그 이외의 자연수는 나눌 때 나머지가 0 이 나오기 때문이다.

[예시] 처럼 nums가 정렬되어 있을 때, 아래와 같이 search가 이루어 져야 한다.

(1, 3) or (3, 1) = O
(1, 2) or (2, 1) = O
(2, 3) or (3, 2) = X

다른 예제인 [1, 2, 4, 8]도 확인해 본다.

1, 8  = O
1, 4  = O
1, 2  = O

2, 8  = O
2, 4  = O

4, 8  = O

해결 전략

현재 최적화 하는 방식은 떠오르지 않으니 brute forcing 방법으로 제일 큰 부분집합을 구해보자.

부분 집합을 구하기 위해 two-pointer 전략을 이용한다. 포인터 변수인 start, end를 바탕으로 nums의 모든 부분집합을 탐색한 후 해당 부분집합이, 조건을 만족한다면 최대 길이 값의, 배열로 업데이트 한 후 반환한다.

end_pointer를 고정시킨 후 start_pointer를 탐색하는 것이 좀 더 가독성 있다고 생각하여 아래처럼 검색해본다.

for end_idx in range(len(nums)):
    for start_idx in range(end_idx):
        # start_idx 부터 end_idx 까지 item 검색 가능

dynamic programming 이용

위의 문제는 dynamic programming을 이용할 수 있다. end_idx 를 추가할지 말지를 조건을 비교하여 만족한다면 추가시킨다.

그 전에, nums 배열이 정렬되어 있으면 nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0를 비교하지 않아도 nums[end_idx] % nums[start_idx] == 0 만 비교하면 된다. (단, end_idx > start_idx)를 항상 만족한다.

answers에는 해당 idx까지의 부분집합의 최대 개수인 item이 들어있다. nums[end_idx]만 조건만 맞다면, 기존에 있던 answers[start_idx] +1 값보다 길이가 길 경우 업데이트 해주면 해당 idx 별로 최대 값을 보장해 줄 수 있다.

    if nums[end_idx] % nums[start_idx] == 0 and len(answers[end_idx]) < len(answers[start_idx]) + 1:
        answers[end_idx] = answers[start_idx] + [nums[end_idx]]

#two-pointer

Comments