라인스위핑
- 너무 추상적인 내용이지만, 문제를 풀면서 알아보자.
구체적인 설명.
이 문제를 대하는 태도
-
1)문제를 보면, vector의 공간이 2억이 된다.
-
2) 2중 for문으로 이렇게 하는 순간 시간복잡도 초과다.
-
3) 처리를 함에 있어서 묶음으로 하고 있따.
=> 결론 : 라인스위핑 문제다.
라인스위핑 핵심.
-
공식
-
이 문제에서 보면, 주어진 stations 과 시작인덱스 값을 가지고 진행하면 된다.
-
어떻게 하면 묶음으로 한번에 처리하면서 stations 의 영역에는 건들지 않으면서 기지국을 설치할까?? 가 관건이다.
사고 핵심, 그리고 코드
-
1에서 5까지 처리하고 6으로 이동해야 하는데 , 이때는 station값보다 작은 경우에 속한다.
-
그 다음에 6에서 12로 넘어가는 겨우를 생각해야 한다.
-
그런데 여기서 잘 생각해보면, 굳이 기지국 영역인 7,8,9,10,11 을 침범해도 된다.
-> 즉 진행하는쪽에서 하나의 묶음으로 생각하는데, station의 최저 영역에 걸리면 진행하는 pos를 다르게 설정해서 진행한다는 거다.
결론
: pos를 어떻게 해야 12로 위치해서 다시 진행할까?? 가 중요하다.
- 코드
만약에 이렇게 생각할수 잇다.
- 9번이 아닌 10번에 기지국이 있다고 한다면, 6번이 아닌 7번에다가 설치하면 좋을까? 생각할 수 있지만, 7번에다가 설치해봤자고 해서 이미 설치된 8,9,10,11,12 영역을 뛰어넘지 못하므로, 6번에다가 설치해도 된다!
🔥🔥🔥