junow 쇠막대기

[Junow]

42585. 쇠막대기

문제링크

메모리 (KB)	시간 (ms)
3.9mb	0.4ms

설계

기존에 푼 코드가 있었는데 주식가격이랑 비슷해보여서 고쳐서 다시품 원래는 O(N^2) 같은 코드였는데 O(N) 으로 바꿔본다 N 이 최대 100000이기 떄문에 원래 N^2 이면 시간초과인데 운이 좋았었나보다.

for loop 을 한바퀴 돌면서 처리할 수 있는데 [i-1], [i+1] 인덱스를 참조하는 코드는 모든 괄호가 쌍을 이룬다는 조건때문에 에러가 나지 않을 것이다.

1. 여는 괄호다

   1. 다음이 닫는괄호다 (레이저임)

2. 닫는 괄호다

   1. 이전이 여는 괄호다 (레이저임)

3. 여는 괄호라면 뒤에 나오는 레이저에 의해 자릴것이기 떄문에 answer++

   1. 레이저라면 잘리는 막대기가 아니라서 걍 냅둠

4. 닫는 괄호라면

   1. 레이저라면 지금까지 나온 막대기를 반으로 나누기 떄문에 막대기 수만큼 answer+=sticks
   2. 레이저가 아니라면 막대기 끝남 sticks--

시간복잡도

O(N)