[프로그래머스] 스타 수열

문제 요약

배열 a의 부분 수열 중 가장 긴 스타 수열의 길이를 구한다.

스타 수열은 인접한 두 원소씩 묶었을 때 다음을 만족해야 한다.

• 모든 묶음에 공통으로 포함되는 숫자가 하나 이상 있다.
• 각 묶음의 두 원소는 서로 다르다.

예를 들어 공통 숫자를 0으로 정했다면, 선택하는 모든 쌍은 (0, 다른 수) 또는 (다른 수, 0) 형태여야 한다.

핵심 아이디어

공통으로 포함될 숫자를 star라고 고정해 보자.

star를 포함하면서 두 원소가 다른 인접 구간만 스타 수열의 한 쌍으로 사용할 수 있다.

a[i] != a[i + 1] 이고
a[i] == star 또는 a[i + 1] == star

이 조건을 만족하는 인접 구간을 간선으로 생각한다. 같은 위치를 공유하는 두 간선은 동시에 고를 수 없으므로, 각 star에 대해 서로 겹치지 않는 간선을 최대한 많이 고르면 된다.

간선의 시작 위치를 앞에서부터 확인하면서, 이전에 고른 간선과 겹치지 않는 첫 간선을 선택하는 그리디가 최적이다.

모든 숫자를 따로 순회하지 않는 방법

후보 숫자마다 전체 배열을 순회하면 최악의 경우 시간이 너무 오래 걸릴 수 있다.

대신 배열의 이웃한 두 원소 a[i], a[i + 1]를 한 번만 확인한다.

• 두 값이 같으면 어떤 스타 수열의 쌍으로도 사용할 수 없다.
• 두 값이 다르면 이 간선은 a[i]를 공통 숫자로 하는 경우와 a[i + 1]를 공통 숫자로 하는 경우에 모두 사용할 수 있다.

따라서 간선의 시작 위치 i를 두 숫자의 목록에 각각 추가한다.

[5, 2, 3, 3, 5, 3]

인덱스 0의 (5, 2) -> 5와 2의 간선 목록에 0 추가
인덱스 1의 (2, 3) -> 2와 3의 간선 목록에 1 추가
인덱스 2의 (3, 3) -> 무시
...

각 간선은 최대 두 번만 저장되므로, 전체 처리량은 선형이다.

풀이 과정

1. 값마다 사용할 수 있는 간선 시작 위치 목록을 만든다.
2. 배열의 이웃 원소가 다르면, 해당 간선의 시작 위치를 두 값의 목록에 추가한다.
3. 각 값의 간선 목록을 앞에서부터 확인한다.
4. 이전에 선택한 간선과 겹치지 않는 간선을 선택한다.
5. 선택한 간선 수에 2를 곱해 스타 수열 길이로 변환하고 최댓값을 갱신한다.

Python 코드

def solution(a):
    length = len(a)

    # a의 원소 범위는 0 이상 length 미만이다.
    edges_by_value = [[] for _ in range(length)]

    # 서로 다른 이웃 원소로 이루어진 간선을 두 값의 후보 목록에 저장한다.
    for index in range(length - 1):
        left = a[index]
        right = a[index + 1]

        if left == right:
            continue

        edges_by_value[left].append(index)
        edges_by_value[right].append(index)

    answer = 0

    for edges in edges_by_value:
        pair_count = 0
        last_selected_edge = -2

        # edges는 인덱스 순서대로 추가되어 이미 정렬된 상태다.
        for edge_start in edges:
            # edge_start와 edge_start + 1 간선이 이전 간선과
            # 같은 원소를 공유하지 않을 때만 선택할 수 있다.
            if edge_start > last_selected_edge + 1:
                pair_count += 1
                last_selected_edge = edge_start

        answer = max(answer, pair_count * 2)

    return answer

코드 설명

간선 시작 위치가 i라면, 이 간선은 a[i]와 a[i + 1]을 하나의 쌍으로 선택한다.

따라서 시작 위치가 연속된 두 간선 i, i + 1은 a[i + 1]을 공통으로 사용하므로 동시에 고를 수 없다.

if edge_start > last_selected_edge + 1:

이 조건은 현재 간선이 이전에 선택한 간선과 원소를 공유하지 않는지 확인한다.

예를 들어 star = 5이고 가능한 간선 시작 위치가 [0, 3]이라면, 두 간선은 겹치지 않으므로 2쌍을 선택할 수 있다. 결과 스타 수열의 길이는 2 * 2 = 4다.

시간 복잡도

N을 배열 a의 길이라고 하자.

• 인접한 원소 확인: O(N)

• 저장된 간선 순회: 각 간선은 최대 두 값의 목록에만 들어가므로 O(N)

• 시간 복잡도: O(N)

• 공간 복잡도: O(N)

정리

스타 수열의 공통 숫자를 기준으로, 그 숫자를 포함하는 서로 다른 이웃 원소 쌍을 간선으로 바꿔 생각하면 된다. 각 숫자에 대해 겹치지 않는 간선을 앞에서부터 고르는 그리디를 적용하면, 후보마다 전체 배열을 다시 순회하지 않고도 가장 긴 스타 수열을 구할 수 있다.