코딩테스트 스터디 - 프로그래머스 스타수열 (python)

문제

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

요약

아래 조건을 만족하는 가장 긴 부분 수열 (스타 수열)을 찾는 문제입니다.

1. 부분 수열은 원래 수열에서 원소를 몇개 제거해 얻을 수 있는 수열이다.

2. 수열의 길이가 짝수이고, {a0, a1}, {a1,a2}...의 교집합의 원소가 1개 이상이다. 즉, 2개마다 같은 숫자가 들어가있어야한다. 또, 두 개씩 짝지어진 숫자가 같은 숫자면 안된다.

의식의 흐름

일단 두 개씩 짝지었을 때 모든 쌍에 포함되는 숫자가 1개 있어야된다는 것에 집중했습니다.

그러면 전체 수열의 숫자 중 1개를 골라, 해당 숫자를 모든 쌍에 포함시켜 만들 수 있는 최대 수열을 O(N)에 구할 수 있습니다.

가장 많이 등장한 숫자부터 확인해보면 되겠지만, 결국엔 수열에 들어있는 모든 숫자로 만들 수 있는 최대 스타수열을 다 확인해줘야합니다.

그러면 O(N^2)이 되고, 수열 길이가 50만으로 나왔기 때문에 시간 초과가 날 것입니다.

 

O(N)보다 작은 시간만에 스타수열의 길이를 구하기 위해 공통으로 들어갈 숫자를 O, 그 외를 X로 표시해봤습니다.

혹시 공통 숫자의 수 * 2 처럼 쉽게 구할 수 있는지 알아보기 위함이었습니다.

그러면 각 숫자별로 등장 횟수를 구하는 순회를 하면서, 빠져야할 원소들을 빼주는 방식으로 계산할 수 있을 것 같았습니다.

예를들어 OXXO 인 경우는 OX , XO로 2쌍을 만들 수 있지만, OXXXO는 X가 하나 빠져야합니다.

이렇게 숫자가 빠져야하는 경우를 여러가지 나열해봤는데, 패턴을 특정하기 어려웠습니다.

 

그래서 점수제를 떠올렸는데, 수열을 쭉 순회하면서 O를 만나면 -1, X를 만나면 +1을 기록합니다.

O와 X가 짝지어지면 0점이 되고, O가 하나 더 많다면 -1점이 되는 식입니다.

그러다가 점수가 +2가 되려고하거나 -2가 되려고하면, 해당 O 또는 X는 제거되어야합니다.  연속해서 2개 더 많게 나오는 경우 해당 숫자는 버려야하기 때문입니다.

예를들어, XOOOXXOXXXO 를 순회하면서 점수를 계산하면 아래처럼 됩니다.

X	O	O	O	X	O	X	X	X	O
1	0	-1	-1 (2가 되려했으므로 제거)	0	-1	0	1	1 (-2가 되려했으므로 제거)	0

그러면 총 10개의 숫자 중 2개가 제거되어야 한다는 점을 알 수 있습니다.

이 점수 방식을 다르게 해석하면, 한 칸 씩 순회할 때마다 점수를 +1 해주고 O를 만날때 -2 (1-2 = -1)를 한다고 생각할 수 있습니다.

그리고 마지막에 남은 점수에 따라 전체 길이에 +1이나 -1를 해주면 됩니다.

 

게다가 이 방식을 수열에 등장하는 모든 숫자에 대해 한다고 생각하면, 각 자리마다 숫자 1개에 대해서만 O가 등장합니다.

그러면 O가 등장한 자리에서만 뭔가 연산을 한다면 O(N)에 문제를 해결할 수 있습니다.

그래서 한 칸 순회할 때마다 모든 숫자에 +1를 해주는게 아닌, O를 만났을 때 그 숫자가 마지막으로 만난 O의 index를 기록해, 이번에 만난 O와 지난번의 O 위치 사이를 모두 X로 간주해 점수를 계산할 수 있습니다.

즉, 앞서 했던 O/X 점수제를 하되, X들은 직접 1씩 더해주는게 아닌 새로운 O를 만났을 때, O 사이의 거리를 이용해 X의 점수를 한번에 더해주는 방식입니다.

 

그 과정을 그림으로 표현하면 아래와 같습니다.

	0	3	3	0	7	2	0	0	0	0
0	a			d			g	h	i	j
2						f
3		b	c
7					e

a : -1점

b : -1점, 마지막 3(만난적없음)으로부터 1칸 떨어져있으므로 1 -> 0점

c : -1점, 마지막 3으로부터 0칸 떨어져있으므로 0 -> -1점

d : -1점, 마지막 0으로부터 2칸 떨어져있으므로 2 -> 기존 -1 -1 + 2 = 0점

e : -1점, 마지막 7(만난적없음)로부터 4칸 떨어져있으므로 4 -> 3점

f : -1점, 마지막 2(만난적없음)로부터 5칸 떨어져있으므로 5 -> 4점

g : -1점, 마지막 0으로부터 2칸 떨어져있으므로 2 -> 기존 0 - 1 + 2 = 1점

h : -1점, 마지막 0으로부터 0칸 떨어져있으므로 0 -> 기존 1 -1 = 0점

i : -1점, 마지막 0으로부터 0칸 떨어져있으므로 0 -> 기존 0 -1 = -1점

j : -1점, 마지막 0으로부터 0칸 떨어져있으므로 0 -> 기존 -1 -1 = -2점이므로, 해당 숫자가 0을 공통숫자로하는 스타수열에서는 빠져야함. -> 점수는 -1점

이렇게 점수를 계산하며 각 숫자별로 점수가 -2나 +2가 될때마다 기록해, 해당 숫자를 공통숫자로 하는 스타수열을 만들 땐 숫자가 몇 개 빠져야하는지 알 수 있습니다.

 

 

구현

자료구조

순회를 하면서 각 숫자별로 몇가지 정보를 기록해야합니다.

1. 현재까지의 점수 (-1~1)

2. 마지막으로 같은 숫자를 만난 Index ( 해당 숫자를 만났을 때, 현재 index - 여기에 기록한 index - 1 = 그 사이의 X 개수)

3. 빠져야할 숫자 수 (점수가 +2 또는 -2가 됐을 때마다 1씩 증가)

 

해당 항목을 수열에 등장하는 모든 숫자에 대해 기록해야합니다.

알고리즘

위에 설명한 알고리즘 그대로, 각 숫자별로 정보를 기록하는 table을 만든 뒤,

한 칸씩 순회하며 만나는 숫자의 정보를 수정해줍니다. 그 단계는

1. 이전의 X들에 대한 처리 (마지막 O 의 index를 이용해 점수 더하기, 초과분 기록)

2. O에 대한 처리 (index기록, 점수 더하기, 초과분 기록)

 

그리고 끝까지 순회하고나면, 모든 숫자들이 마지막으로 만난 O 이후는 전부 X이므로 알맞은 계산을 해주면 됩니다.

코드

오래 고민하다가 뭔가 계속 새로운 발견을 하는 기분이었어서 성취감이 폭발하는 문제였습니다.

 

'''
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/70130
'''
def solution(a):
    #특정 숫자를 공통숫자로 정하는 스타수열을 계산한다고 했을때, X:다른숫자, O:내숫자
    #X는 +1, O는 -1 해서 +2나 -2가 안되게 하면 됨 > 이렇게 되는 경우 그 칸 무시
    #표 +- 점수 / 현재까지 길이 기록 : +2나 -2가 되려고 하는 경우에 1 빼주면됨
    #근데 한칸 갈때마다 +1, O를 만나면 -2를 시킨다면 -> 똑같음.
    #한 칸 순회할때마다
        #자기숫자표에, 마지막으로 O였던 index를 저장해서
        #현 index - 마지막Oindex = 현재까지 연속한 X수 -> 점수 구할 수 있음
    answer = -1
    nums = set(a)
    table = {}
    for n in nums: 
        table[n] = [0, -1, len(a)] #+-점수, 마지막Oindex, 현재까지 길이
        
    for i in range(len(a)):
        #이전 X들에 대한 처리
        others = i - table[a[i]][1] - 1 #이번 O 전에 있던 X 개수
        table[a[i]][0] -= others #그 수만큼 점수 빼줌
        if table[a[i]][0] < -1:
            table[a[i]][2] -= -1 - table[a[i]][0] #점수 초과분을 len에서 빼줌
            table[a[i]][0] = -1
        #O에 대한 처리
        table[a[i]][1] = i
        table[a[i]][0] += 1
        if table[a[i]][0] > 1: #점수 초과분을 len에서 빼줌
            table[a[i]][0] = 1
            table[a[i]][2] -= 1
            
    #다 돌고 나서
    for n in nums:
        #1점 : 다 매칭하고 O가 하나 남았고, 그 뒤에 X들이 있단 뜻 = 그 뒤의 X 하나 빼고 전부 빼기
        #0점 : 다 매칭하고 , 그 뒤에 X들이 있단 뜻 = 뒤의 X들만큼 전부 빼기
        #-1점 : 다 매칭하고 X가 하나 남았고, 그 뒤에 X들이 있단 뜻 = 그 뒤의 X + 1개 빼기
        # -> (Oindex 부터 남은 수 - score) 만큼을 len에서 빼주면됨
        left = len(a) - table[n][1] - 1 #이번 O 전에 있던 X 개수
        table[n][2] -= max(left - table[n][0], 0)
        answer = max(answer, int(table[n][2]/2))
    
    return answer * 2