[질문] 최근 코포 B번 (에듀케이셔널) 투포인터로 어떻게 푸는거지?

[익명(66.75)]

뉴비인데 투포인터나 binary 서치나풀 수 있다는데 방법을 모르겠습니다 ㅠㅠㅠ

에디토리얼 봤는데 풀이가 안떠오릅니다....

도와주십쇼 행님들 ㅠㅠㅠ

[Gravekper(gravekper)]

일단 에디토리얼의 풀이는 바이너리 서치도 투포인터도 아닌 별개의 해법임

[Gravekper(gravekper)]

바이너리 서치: 1,2,3 각각이 몇번 등장하는지 부분합을 미리 구해놓고, i=0부터 n-1까지 모든 시작점부터 1,2,3이 각각 적어도 한번씩 등장하는 구간 i...j를 이분 검색으로 찾는다.

[Gravekper(gravekper)]

투포인터: 시작점 i=0에서부터 왼쪽부터 세어서 제일 먼저 (1,2,3)을 만족하는 구간 (0..j)를 찾는다. 찾았으면 i를 1 증가시켜서 구간(1..j)를 찾는다. 이 때 1..j가 (1,2,3)을 만족하지 않으면 j를 양의 방향으로 한 칸씩 이동시켜서 적절한 (i..j)를 찾는다. j<n인 동안 반복해서 찾은 구간들 중 가장 짧은 것이 답.

[Gravekper(gravekper)]

그리고 이번 기회에 부분 합에 대해 공부해보는 것도 추천

[익명(66.75)]

[익명(66.75)]

감사합니다 Gravekper님! 친절한 답변 감사합니다!!