[일반] hacking phase에도 질문글 가능한가요? (E번)

[익명(119.70)]

e 부분합 이용하는 알고리즘 설명해주실 분 계신가요?

[ㅇd(124.111)]

숫자별로(1~200) 부분합 배열을 만들어놓으면 특정 구간에서 숫자 개수를 O(1)로 구할 수 있음. 그리고 숫자별로 인덱스를 벡터에다가 넣어둠. 이게 전처리. 그리고 팰린드롬이 대칭이니까 모든 숫자에 대해 앞쪽과 뒤쪽에서 하나씩 숫자를 뽑으면서, 그 가운데 부분에서 가장 개수가 많은 숫자를 구해줌. 그렇게 모든 경우 검사해서 최댓값 찾으면 됨.

[익명(119.70)]

111111223211111 과 같은 배열에서 양쪽에서 1을 하나씩 뽑으면 그 사이구간에서 1을 또 뽑을지 다른 연속된 수를 고를지 정해야해서 가짓수가 2가지씩 늘어가는거 같은데 시간초과가 나지 않는건가요?

[익명(223.33)]

모든 숫자는 결과적으로 한번씩만 뽑힘. 그리고 숫자를 뽑을때마다 그 사이의 가장 많이 등장하는 숫자를 부분합을 이용해서 O(1)로 구하고. 그러니까 시간복잡도는 대충 O(200N)이 될거임. - dc App

[익명(223.33)]

그리고 본 질문에 대해 대답하자면 양쪽에서 1을 뽑고 그 사이에서 1을 또 뽑아도 상관없음. 그럼 11/11111/11 꼴이 될텐데 그것도 답 후보중 하나니까. - dc App

[익명(119.70)]

11222333333333322211같은 수열을 뽑게 되는 경우는 없는건가요?

[익명(223.62)]

문제 읽어보면 그건 조건에 안맞음. aaabbbaaa꼴. 즉 최대 2개의 숫자로 이뤄져있어야함. - dc App

[익명(119.70)]

답변 감사드립니다 ac받으신 분들 코드 천천히 읽어봐야겠네요