본문 바로가기

Programming Problems/Arrays

모든 단어가 포함된 최소 범위 찾기 Q

job : 5,9,17

in : 4,13,18

google : 8,19,21


>> 17,18,19 ans : 3


처음부터 최솟값을 하나씩 들어올리면서 길이를 재계산한다. 모두 마지막에 닿을 때까지


O(NlogN^K) ( 힙으로 최솟값을 트래킹한다 )


정당성 : 최솟값을 증가시키기 않고 다른 것을 증가시키면 최솟값이 그대로 남게 되어 결국 범위가 증가하거나 같게 된다. 

최솟값이 존재한다고 가정하면 최솟값이 아닌 것을 ...


모르겠다 더 생각해 보자


이런 경우 우리는 "이 검색 방식이 최솟값을 지나치지 않는다" 를 확인하면 된다.


만약 우리가 i -> k가 최솟값이라고 결론내렸는데 사실 i->k'가 최적의 솔루션이라고 생각해 보자. 이때, i,k,k' 중에 k'가 최솟값이 아니므로 k'를 k로 옮기지 않은 상태에서 i에 도달했을 것이다. 따라서, 이 검색 방식으로는 반드시 최적의 솔루션 i->k'를 지나치게 된다.