[Leetcode] 1375. Bulb Switcher III

문제 : https://leetcode.com/problems/bulb-switcher-iii/

---

1 ~ n 까지 번호가 매겨진 n개의 전구가 왼쪽에서 오른쪽으로 나열된 방이 있고, 전구번호를 가진 light 배열이 있다. 모든 전구들은 전구가 꺼져있다. k(0 ~ n-1) 번째에 light[k] 전구를 켠다. 만일 전구가 켜져 있고 해당 전구의 좌측에 있는 모든 전구들 또한 켜져 있다면 전구의 색들이 파란색으로 바뀐다. 켜진 전구들이 모두 파란색이 되는 순간의 횟수를 구해라.

---

k번째에 켜진 모든 전구들이 파란색으로 변경되는 순간은 1 ~ k+1 번째의 전구가 모두 켜져있는 경우밖에 없다. 한 번엔 하나의 전구만 켜지고 전구의 번호는 겹치지 않으므로 이때동안 켜졌던 전구번호중 가장 큰 값이 k+1인 경우가 켜진 전구들이 모두 파란색이 되는 경우가 된다.

따라서 light 배열을 앞에서부터 탐색하면서 전구번호의 최대값이 k+1이 되는 경우 정답을 1씩 더해준다.

 

시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1375.%20Bulb%20Switcher%20III.cpp