[programmers][월간 코드 챌린지 시즌1] 스타 수열

문제 : programmers.co.kr/learn/courses/30/lessons/70130

---

 

조건들 중 정답에 가장 큰 영향을 끼치는건 스타 수열의 교집합 숫자이다.

a 배열을 탐색하면서 같은 수를 가지는 배열 인덱스를 저장한다.

즉, numbers 2차원 배열을 만드는데 numbers[number] 는 a 배열에서 number 값을 가지는 인덱스들을 저장한다.

[5,2,3,3,5,3]을 예로들면 numbers[2] = {1}, numbers[3] = {2,3,5}, numbers[5] = {0,4}가 저장된다.

 

이제 numbers 배열을 탐색하면서 number의 짝이 최대 몇개나오는지 구하고 이들 중 최대값이 정답이 된다.

[0,3,3,0,7,2,0,2,2,0]을 예로들어보자.

numbers 배열을 만든 뒤 교집합으로 0을 가지는 스타수열의 길이를 구해보자.

numbers[0] = {0,3,6,9} 이다.

교집합수(0)이 아닌 값으로 선택될 수 있는 수가 될 수 있는 최저 인덱스를 left라 하자. 초기값은 0이다. 즉, a 배열에서 left 이상 인덱스 원소는 스타수열에 포함될 수도 있다는 뜻이다.

 

만약 탐색중인 numbers[0]의 배열 원소(a 배열의 인덱스. let, index)가

[그림1]

i) left보다 크다면 left를 짝으로 가질 수 있으므로 스타수열에 포함가능하다. ([그림1]) 그림의 예시는 [5,2,3,3,5,3] 이다.

[그림2]

ii) left보다 작거나 같다면 a 배열에서 index 왼쪽에 있는 배열들은 짝으로 가질 수 없다는 뜻이다.  ([그림2])

따라서 borrow라는 flag를 하나 두고 다음에 판단하겠다고 true로 갱신한채 다음 index를 탐색한다.

다음 값 탐색시 borrow 플래그가 true라면 이전 값이 스타배열으로 채택될 수 있는지 다시 판단한다.

만약 현재 탐색 중인 index가 left보다 크다면 left 값과 이전 탐색한 index가 스타수열로 채택 가능하다. 이제 left 값은 이전 index와 스타수열에 채택되었으므로 다시 사용하면 안되기에 left + 1 해준다. 

이 후 borrow 플래그는 다시 false로 하고 현재 탐색중인 index가 스타수열로 채택될 수 있는지 계속 탐색한다.

 

[0,3,3,0,7,2,0,2,2,0]을 예로들어, 위 로직을 적용해보자.

numbers[0] 배열을 앞에서부터 탐색한다.

1) left = 0, index(numbers[0][0]) = 0. borrow = false.

left >= index 이기에 borrow 플래그를 true로 바꾸고 left도 index+1로 갱신한다. left는 항상 index+1로 갱신해야 한다.

2) left = 1, index(numbers[0][1]) = 3. borrow = true.

borrow가 true이기 때문에 이전 index가 스타수열이 될 수 있는지 먼저 판단한다.

left < index이기 때문에 이전 index도 스타수열이 될 수 있다. => {0, 3}

left는 2로 갱신된다. borrow는 false.

이제 현재 index도 스타수열이 될 수 있는지 판단한다.

left(2) < index이기 때문에 현재 index도 스타수열이 될 수 있다. => {3, 0}

3) left = 4, index(numbers[0][2]) = 6. borrow = false.

left < index. 스타수열 가능. => {2, 0}

4) left = 7. index(numbers[0][3]) = 9. borrow = false.

left < index. 스타수열 가능. => {2, 0}

 

스타수열의 길이는 8이다.

 

시간복잡도는 O(|a|).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%EC%8A%A4%ED%83%80%20%EC%88%98%EC%97%B4.cpp