https://school.programmers.co.kr/learn/courses/30/lessons/70130?language=python3

수열 a의 부분수열 중에서, 길이가 2이상 짝수이고, 앞에서부터 2개씩 나눈 부분집합들의 교집합의 원소가 1개 이상인 수열이 있으면 스타수열이라고 할 때 가장 긴 스타수열의 길이를 구하는 문제이다.

Python

시도 - 1 - LIS 방식

def solution(a):
    answer = 2
    
    if len(a) <= 1:
        return 0
    
    d = [2]
    x = []
    
    return answer

def chk_star(list):
    if len(list) <= 1 and len(list) % 2 != 0:
        return False
    chk = [0, 0]
    for i in range(2, len(list)):
        if list[0][0] in list[i]:
            chk[0] += 1
        if list[0][1] in list[i]:
            chk[1] += 1
            
    if chk[0] == len(list) // 2 or chk [1] == len(list):
        return True
    else:
        return False

만들다만 코드이다. 가장 긴 증가하는 부분수열이 생각나서 앞에서부터 숫자 한 개씩 넣으면서 길이가 짝수이면 chk_star라는 함수를 통해 스타수열인지 확인하고 아니라면 다음 숫자 넣는 방식으로 해볼까 했다.
LIS에서는 한 개씩 숫자를 비교하고 판단했는데, 여기서는 숫자 두 개를 넣어서 판단해야하는 차이점이 있었고, 그 두 개도 연속적인 두 개가 아니라 한 개 넣고 한참 뒤에 추가한 한 개가 스타수열이 될 수도 있고 한다는 점에서 시간복잡도가 엄청날 것 같아서 포기했다. chk_star도 최악의 경우 2n번 비교해야하기에 그걸 모든 숫자에 하면 O(n^2)의 복잡도가 날 것 같아서 버렸다.

시도 2 - 숫자 넣어보기

질문하기의 글 중 파이썬 탐욕법적 접근라는 글을 참고했다.

어차피 교집합의 숫자가 한 개이기 때문에 숫자 한 개를 기준으로 앞 뒤에 다른 숫자 한 개 있는지 비교하고 있으면 스타수열의 부분집합으로 간주해서 개수를 더하는 방식으로 최대 길이 구하는 방식이다.

def solution(a):
    answer = -1
    
    nums_idx = [[] for _ in range(max(a) + 1)]
    
    for idx, n in enumerate(a):
        nums_idx[n].append(idx)
        
    for n, idxes in enumerate(nums_idx):
        used = set()
        for i in idxes:
            if (i - 1) >= 0 and (i - 1) not in used and i not in used and a[i] != a[i - 1]:
                used.add(i)
                used.add(i - 1)
            elif (i + 1) < len(a) and (i + 1) not in used and i not in used and a[i] != a[i + 1]:
                used.add(i)
                used.add(i + 1)
        answer = max(answer, len(used))
                
    
    return answer

먼저 nums_idx라는 리스트를 만들어서 0부터 최대 숫자만큼의 빈 리스트를 생성했다. 그리고 그 다음 for문을 통해서 각 숫자에 해당하는 리스트에 위치 정보를 저장했다.

이렇게 만든 위치정보를 돌면서 탐색을 시작했는데, used라는 집합을 만들어서 이미 집합 만드는데 사용된 index인지 파악했다.

그 다음 조건문으로는 먼저 왼쪽 원소에 대해서 0이상이고, 사용되지 않았고, i도 사용 안 됐고 둘이 숫자가 서로 다르다면 used에 추가했고 왼쪽 원소가 실패하면 오른쪽 원소에 대해 같은 절차를 진행했다.

마지막으로 이렇게 집합에 추가된 index의 개수를 세서 answer와 비교했다.