insu_nym   2년 전

우선 인풋을 string inp에 받고, idx: 0 ~ n - 1 까지 inp[idx]를 확인하며 laser와 스틱을 찾게끔 구현했습니다.

1. inp[idx]가 '(' 인 경우 벡터에 idx를 푸시
2-a. inp[idx]가 ')' 이며 v.back() == idx - 1일 경우 레이져로 판단하고
2-b. inp[idx]가 ')' 이며 v.back() 이 < idx - 1보다 작은 경우 쇠막대로 판단하고 stick[v.back()] 부터 stick[idx]까지 1을 더해줘서
laser 배열과 stick 배열을 만들어 줬습니다. O(n2) 맞나요?
아마 여기서 시간 초과가 나는거 같은데 고수님들 조언 부탁 드립니다 ㅜㅠ

DryType   2년 전

네 극단적인 경우에  for문이 100000 + 99998 + 99996 + ... 되면서 시간초과가 나겠어요

꼭 문제처럼 막대기를 구현하지 않아도, 레이저를 쐈을때 막대기가 추가되는 갯수를 생각하면 풀수있습니다.

insu_nym   2년 전

아 그렇게는 생각 못했네요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.