문제

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

풀이

교집합 원소가 될 수 찾기

접근한 방법은 문제에서 제시한 스타수열의 조건을 만족하는, 배열안에서 만들어지는 집합의 교집합의 원소가 될 수 있는 숫자를 선택하고,
이 숫자를 교집합의 원소로 할 때 만들 수 있는 가장 긴 부분 수열의 길이를 구하는 방법이다.

처음에는 완전 탐색으로 풀려고 했으나,
교집합의 원소가 될 숫자를 정하고 나면 그냥 입력으로 주어진 배열을 순회하며
조건에 맞게 숫자를 선택하여 스타수열의 길이를 구할 수 있었다.

효율성 개선하기

그러나 위 방법에서 효율성을 개선하지 않으면 시간초과를 면하기 어렵다.
우선 교집합의 원소가 될 수 있는 수는 수열 a에 존재하는 모든 종류의 수이다.

그 중 어떤 수 k의 갯수가 현재까지 구한 "가장 긴 스타수열의 길이 $\div$ 2" 보다 작다면,
k를 교집합의 원소로 하는 경우는 계산할 필요가 없다.
왜냐면 k가 교집합의 원소라면, 그렇게 만들어진 스타수열의 각 부분집합({$a_0$, $a_1$}, {$a_2$, $a_3$}, ... , {$a_{n-1}$, $a_n$}) 에는 모두 k가 포함되어있어야 할 것 이고,
따라서 부분집합의 갯수는 항상 배열 a에서의 k의 갯수보다 작거나 같을것이다.

그런데 이미 구해진 스타수열이 가지는 부분집합의 갯수가 배열 a에서의 k의 갯수보다 같거나 많다면,
k를 교집합의 원소로 하는 탐색으로 나올 수 있는 스타수열의 최대 길이는 현재 구해진 스타수열의 최대길이 이하이다.

따라서 이와같은 상황에서 불필요한 연산을 하지 않기 위해
각 원소가 배열 a에서 몇개 존재하는지 저장한 뒤,
이후 스타수열의 최대길이를 구하는 연산에서
현재 구해진 최대 길이가 가지는 부분집합의 갯수(= 최대 길이 $\div$ 2) 보다 적은 갯수를 가지는 숫자는
교집합 원소의 후보에서 제외시킬 수 있다.

코드1

def solution(a):
    answer = 0
    num_count = dict()
    for i in range(len(a)):
        if a[i] not in num_count:
            num_count[a[i]] = 0
        num_count[a[i]] += 1
        
    for (num, val) in num_count.items():
        if answer >= val*2: continue
        idx, count, length, pre = 0, 0, 0, -1
        while idx < len(a):
            if count % 2 == 0:
                count += 1
                pre = a[idx]
            else:
                if check(a[idx], pre, num):
                    count += 1
                    length += 2
            idx += 1
        answer = max(answer, length)
    return answer

def check(current, previous, common):
    return (current == common or previous == common) and current != previous    

위 코드에서 스타수열을 만들어주기 위해서
두번째 원소를 선택할 때 전체 길이를 2씩 증가시켜주었다.
또한 공통으로 들어갈 원소를 최소 한번은 선택하면서 두 원소가 같지 않도록 하기 위해
해당 조건을 check() 함수를 통해 분리했고,
만약 스타수열의 각 집합의 두번째 원소를 선택해야 하는 상황에서는
조건을 만족할 때 까지 배열을 순회한다.

탐색 방법의 개선 - 1

그러나 이렇게 복잡하게 할 필요 없이, 그냥 인접한 수를 배열에 추가시킬 수 있는지 여부만 판단해 주면 되는것을 알았다.

이미 교집합의 원소가 결정되어있는 상태에서 스타수열의 길이를 구하는 것이기 때문에,
스타수열에서 같은 집합안에 있는 두 수 중 하나만 교집합의 원소이기만 하면 된다. (교집합의 원소가 아닌, 선택 가능한 수는 어떤 수가 와도 상관 없다.)

따라서 다음과 같이 코드를 수정할 수 있다.
풀이에 사용된 논리는 동일하기 때문에 시간 복잡도는 동일하다.

코드 2

def solution(a):
    answer = 0
    num_count = dict()
    for i in range(len(a)):
        if a[i] not in num_count:
            num_count[a[i]] = 0
        num_count[a[i]] += 1
        
    for (num, val) in num_count.items():
        if answer >= val*2: continue
        length = 0
        i = 1
        while i < len(a):
            if a[i] == a[i-1] or (a[i] != num and a[i-1] != num):        
                i += 1
                continue
            i += 2
            length += 2
        answer = max(answer, length)
    return answer

배열을 순회하며, 스타 수열의 조건에 맞지 않다면 다음 원소를 탐색하고,
조건에 맞는 인접한 두 원소를 찾았다면 인덱스를 2증가시킨다.

인덱스를 2씩 증가시킬 수 있는 이유는
조건에 맞는 인접한 두 원소를 찾은 경우를 살펴보면 알 수 있다.
일단, 두 원소 중 교집합의 원소로 삼은 수를 $x$, $x$가 아닌 수를 $w$라고 하자.
$x = a_i$, $w = a_j$ 일 때,
1) $i < j$ 인 경우
$w$를 이미 선택했기 때문에, $a_{j+1}$이 $x$라고 해도 이후에 $w$는 선택될 수 없다.
2) $i > j$ 인 경우
마찬가지로 $x$를 이미 선택했기 때문에, $a_{i+1}$이 $x$가 아닌 수 라고 해도 $x$는 선택될 수 없다.

그렇기 때문에 다음 수가 아닌 다다음수 부터 탐색을 진행할 수 있다.

탐색 방법의 개선 - 2

이 풀이는 다른 분들의 코드를 보고 이해한 내용을 기록한 것이다.

다른 사람의 풀이를 보다가 $O(n)$으로 정답을 계산하는 코드를 몇개 발견했다.
아래는 그 중 하나이다.

코드 3

def solution(a):
    ans = 0
    dic = {}
    check = {}
    for i in range(len(a)):
        dic[i] = 0
        check[i] = -2

    for i in range(len(a) - 1):
        if a[i] != a[i+1]:
            if check[a[i]] != i-1:
                dic[a[i]] += 1
                check[a[i]] = i
            if check[a[i+1]] != i-1:
                dic[a[i+1]] += 1
                check[a[i+1]] = i

    return max(dic.values()) * 2

두개의 딕셔너리를 선언한다.

• 하나(dic)의
  key는 배열 a의 원소이고,
  value로는 key를 교집합의 원소로 했을 때 만들 수 있는 스타수열의 부분집합의 최대 갯수를 갖는다.

• 다른 하나(check)의
  key는 마찬가지로 배열 a의 원소이고,
  value는 key가 사용된 가장 최근 index가 저장된다. 여기서 index는 key의 index가 아닌, 몇번째 순회에서 사용되었는지 를 나타낸다.
  모든 value를 -2로 초기화 한 이유는 구현 방식 때문인데, value를 비교할 때 -1 이상의 수와 비교하게 되기 때문에 이것에 영향을 주지 않는 초기값(-2)로 초기화 한 것이다.

이 풀이의 아이디어는
배열 a의 어떤 수가 '교집합의 원소'가 될 수 있다면,
한번의 순회에서, i번째 원소와 i+1번째 원소를 교집합의 원소 후보로 하는 것이다.

이전 풀이의 "스타수열의 길이를 직전수와의 비교만으로 구할 수 있었던 것"과 같은 논리에서
항상 현재 원소를 기준으로 "현재 숫자와 다음 숫자를 교집합의 원소로 할 수 있는지"를 판단하며,
만약 가능하다면
현재 숫자(i)는 다음숫자(i+1)와 함께,
다음 숫자(i+1)는 현재숫자(i)와 함께 스타수열에 들어가는것으로 처리한다.

스타수열의 길이를 구하는 코드만 다시 확인해보자

    for i in range(len(a) - 1):
        if a[i] != a[i+1]:				# 1번
            if check[a[i]] != i-1:		# 2번
                dic[a[i]] += 1
                check[a[i]] = i
            if check[a[i+1]] != i-1:	# 3번
                dic[a[i+1]] += 1
                check[a[i+1]] = i

1번 조건문

현재 원소와 다음 원소가 같은지 확인하는 조건문이다.
두 원소가 같다면 조건에 맞는 수열을 만들 수 없기 때문에
같지 않은 경우에만 이후 과정을 진행한다.

2번 조건문

a[i]가 직전(i-1)에 스타 수열의 길이 계산에 사용되었는지 확인한다.

만약 그렇다면,

• a[i]는 이미 직전에 사용된 원소이므로, 길이 계산에 사용하지 않는다.

그렇지 않다면,

• a[i]를 교집합의 원소로 할 때의 스타수열 부분집합 갯수를 1 늘려준다.
  dic[a[i]] += 1
• 그리고 'i번째에 a[i]를 사용했다' 라는 표시를 한다. check[a[i]] = i

3번 조건문

3번 조건문이 왜 있어야 하는지가 가장 헷갈렸는데,
이 조건문이 있기 때문에 중복없이 스타수열의 길이를 계산할 수 있는 것이다.

먼저 조건문의 내용은 2번 조건문에서 a[i]를 a[i+1]로 바꿔준것과 동일하다.
즉, 'i번째에 a[i+1]을 사용했다' 는 표시를 해준 것이다.

지금은 반복문을 i번째 돌고 있는 중인데, 왜 i+1번째 수에대한 사용 여부를 처리하고 수열의 길이를 갱신하는지에 대한 의문이 드는데,
그 이유는 같은 위치에 있는 숫자를 2번 사용하게 되는 경우를 계산에 넣지 않게 하기 위해서 이다.

수열 a가 다음과 같이 주어졌다고 하자

위의 로직대로 계산한다면 아래와 같은 과정을 거치게 될 것이다.

i=0
a[0]과 a[1]은 같지 않다.
두 수 모두 이번에 처음 나타났으므로 다음과 같이 갱신된다.

a	key	dic[key]	check[key]
a[0]	1	1	0
a[1]	2	1	0

i=1
a[1]과 a[2]는 같지 않다.
check[a[1]] == check[2] == 0 == i-1 이므로 a[2]에 대해서만 갱신된다.

a	key	dic[key]	check[key]
a[0]	1	1	0
a[1]	2	1	0
a[2]	3	1	1

i=2
a[2]와 a[3]은 같지 않다.
check[a[2]] == check[3] == 1 == i-1 이므로 a[3]에 대해서만 갱신된다.

a	key	dic[key]	check[key]
a[0]	1	1	0
a[3]	2	2	2
a[2]	3	1	1

이처럼 i번째 순회에서 a[i]와 a[i+1]의 사용 여부를 모두 계산해 주어서
다음 순회에서 동일한 위치의 값을 2번 사용해서 스타수열을 만드는 경우를 배제할 수 있다.

만약 이렇게 처리하지 않는다면,
위 예시에서 2를 교집합의 원소로하는 스타수열의 길이를 계산할 때 i = 1일 때 a[1]인 2가 중복해서 들어갈 것이다.