Question

파이썬 탐욕법적 접근

우선 문제에서 "{x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다." 라고 하는 것이 있는데, 교집합의 원소의 개수가 2개가 되면 "x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1]"에 위배되기 때문에 1개 입니다.

즉 이 문제는 고정된 원소 a가 있고, 이에 대응되는 원소 b가 존재만 하면 됩니다.
예를 들어서 [0, 3, 0, 3, 0, 3, 0, 3] 이라고 하는 배열에 0을 a에 집어넣어 봅시다.

각 0들을 a1, a2, a3, a4라고 하면, "각각에 a1, a2, a3, a4 옆에(왼쪽 혹은 오른쪽) 원소가 존재 하는가?"를 판별만 하면 됩니다.

이 경우에는 다음과 같습니다.
[a1, 3, a2, 3, a3, 3, a4, 3]

a1은 왼쪽에는 원소가 없고, 오른쪽에 3이 1개 있으므로 이 3을 가져갑니다.
a2는 왼쪽에 원소가 이미 a1이 가져갔으므로 없고, 오른쪽에 3이 1개 있으므로 이 3을 가져갑니다.
a3은 왼쪽에 원소가 이미 a2가 가져갔으므로 없고, 오른쪽에 3이 1개 있으므로 이 3을 가져갑니다.
a4는 왼쪽에 원소가 이미 a3이 가져갔으므로 없고, 오른쪽에 3이 1개 있으므로 이 3을 가져갑니다.

즉 [ak, r]에 해당하는 원소 쌍이 4개 가능하고, 이 4개는 모두 스타 배열의 조건을 충족하기에 길이는 4*2 = 8입니다.
이 때 r은 어떠한 자연수가 되든 상관이 없습니다.

따라서 [ak, r] 쌍을 찾는데 중요한 것은 ak-1과 ak 사이의 거리가 얼마인지, 그리고 이 ak-1이 자신을 기준으로 왼쪽에 있는 원소를 잡아먹었는지, 또는 오른쪽에 있는 원소를 잡아먹었는지를 알기만 하면 됩니다. "값이 아닌 거리 차이를 분석하는 것" 이것이 제일 중요한 포인트 입니다.

예를 들어 [3,1,1,3,5,1,1]에서 a를 1이라고 하면, [3,a1,a2,3,5,a3,a4]가 됩니다. 이제 풀어볼까요?

a1과 a2의 거리 차이는 1 이지만, a1 왼쪽에 공간이 있기에 a1은 가져갑니다
a2는 a1과 거리 차이가 1이기에, 반드시 오른쪽에 공간이 있어야 합니다. 이 경우에 공간이 있기에 a2도 가져갑니다.
a3은 a4와 거리 차이가 1 이지만, a2와 a3 사이 공간이 2 이상입니다. 즉 a2가 오른쪽을 먹어도 a3은 1개를 더 가져갈 수 있기 때문에 a3도 가져갑니다.
a4는 a3과 거리 차이가 1이므로, 오른쪽에 공간이 있어야 하는데 배열의 끝 입니다. 따라서 a4는 가져갈 수 없습니다. 따라서 가져가는 쌍은 [a1, r], [a2, r], [a3, r]이므로 스타 수열 길이는 6입니다.

그렇다면 가장 많은 [ak, r] 순서쌍을 가지는 ak는 무엇일까요? 여기에 그냥 탐욕법을 넣자는 겁니다.
배열 a를 순회하여, 다음의 정보를 저장해야 합니다.

값 p의 개수
값 p가 존재하는 a의 인덱스 목록
값 p 그 자체

그 다음에 "값 p의 개수"를 기준으로 정렬을 1번 합니다.

이렇게 하면 저희는 숫자가 제일 많은 p부터 p가 존재하는 인덱스 목록을 활용하여 [ak, r] 순서 쌍을 찾을 수 있습니다. 그리고 어느 순간 숫자 p의 전부가 순서쌍이 된 스타 수열의 길이가 answer보다 작게 되면, 이 때 이 answer를 반환하면 끝입니다.

이렇게 풀면 시간 초과가 나지 않을까요? 하지만 나지 않습니다. 왜냐하면 고유한 숫자의 개수 * 이 숫자들이 반복되는 횟수의 합이 곧 배열 a의 길이이기 때문입니다.

예를 들어 숫자가 1부터 50만 까지 전부 있다고 하면, 모든 숫자는 오로지 1번만 반복됩니다. 그래서 double-for 루프를 돌려도 O(N)과 다를 바가 없습니다.

반대로 숫자가 1부터 1000까지 있고, 각 숫자가 500번 반복된다고 해도, 첫 번째 루프는 천 번 돌고, 두 번째 루프는 500번 돌기 때문에 O(N)입니다.

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import math
def solution(a):
    answer = -math.inf
    count = [[i,0,[]] for i in range(len(a))]
    if len(a) < 2:
        return 0

    for i, elem in enumerate(a):
        count[elem][1] += 1
        count[elem][2].append(i)

    res = [[elem[0],elem[1]] for elem in count if elem[1] != 0]
    res.sort(key= lambda x : -x[1])

    for elem in res:
        set_num = elem[0]
        idx_list = count[set_num][-1]
        cnt = elem[-1] * 2
        cannot_eat_left_flag = None
        first_flag = True

        if cnt < answer:
            return answer

        if len(idx_list) == 1:
            cnt = 2
            continue

        for i in range(len(idx_list)):
            if first_flag:
                first_flag = False
                if idx_list[i] == 0:
                    cannot_eat_left_flag = True

                    if idx_list[i+1] - idx_list[i] == 1:
                        cnt -= 2

                else:
                    if idx_list[i + 1] - idx_list[i] == 1:
                        cannot_eat_left_flag = True

            elif i == len(idx_list) - 1:
                if idx_list[i] == len(a)-1:
                    if idx_list[i] - idx_list[i-1] == 1:
                        cnt -= 2

                    elif cannot_eat_left_flag:
                        cnt -= 2

            else:
                if cannot_eat_left_flag:
                    if idx_list[i + 1] - idx_list[i] == 1:
                        cnt -= 2
                        cannot_eat_left_flag = True

                    elif idx_list[i+1] - idx_list[i] == 2:
                        cannot_eat_left_flag = True

                    else:
                        cannot_eat_left_flag = False

                else:
                    if idx_list[i+1] - idx_list[i] == 1:
                        cannot_eat_left_flag = True

                    else:
                        cannot_eat_left_flag = False

        if answer < cnt:
            answer = cnt

    return answer

a = [0,0,0,0,0,0,0,0,0,3,1,1,3,5,1,6,1,7]
a = [5, 2, 3, 3, 5, 3]
print(solution(a)) # 8

이정민

2024.6.17 20:35

파이썬 탐욕법적 접근

작성중인 코드―solution.py

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.