[프로그래머스] '22.11.16. Programmers Bell

2가지 색을 가진 종이 존재할 때, 임의로 구간을 자를 경우 두 색의 각각 갯수가 같고 구간 길이가 최대인 길이를 구하여라.

 

종의 색에 따라 1 또는 2가 들어온다.

 

[1, 2, 1, 1, 1, 2, 2, 1]	6
[1, 1, 1, 1, 1, 1]	0
[2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1]	4

1. 누적합을 이용하는 방법

- itertools 안에 있는 accumulate 함수를 사용한다

itertools.accumulate(iterable, func, *, initial=None)

- iterable : list 등과 같은 자료구조

- func : binary function

- initial : 시작하는 값

 

Trick - Important

- 1인 경우 1로 저장, 2인 경우를 -1로 저장한다

- 구간 합을 통해 음수(-)인 경우 해당 구간에 2가 더 많은 것을 알 수 있다.

- 구간 합이 양수(+)인 경우 해당 구간에 1이 더 많은 것을 알 수 있다.

- 구간에 1의 갯수와 2의 갯수가 동일하다는 의미는 다시 누적합이 등장할 때이다.

ex) -1이 처음 나온 경우 이후 -1이 다시 나오면 두 구간 사이 갯수가 동일하다.

 

즉 start에 처음 각 값이 등장하는 인덱스를 저장하여, 이후 end에 인덱스를 저장할 경우, 두 값의 차이가 구간의 길이다.

 

2. dictionary를 사용

- start와 end를 사용하여, 각 값의 value와 index를 저장한다.

- start와 end에서 동일한 값의 index를 꺼내어 최대값을 구하면 그 값이 구간의 최대길이이다.

 

from itertools import accumulate

def solution(bell):

      start = {}

      end = {}

 

     for i, v in enumerate(accumulate([0] + [-1 if b == 2 else 1 for b in bell])):

          if v not in start:

                start[v] = i

          end[v] = i

     return max([end[v] - start[v] for v in end])