leejun51   1년 전

제가 아직 미숙해서 어느 부분에서 시간을 더 줄일 수 있는지 파악이 안됩니다.


선생님들의 조언 부탁드립니다.

byeongkeunahn   1년 전

작성해주신 코드를 요약해보면 작동 원리가 다음과 같아 보입니다.

  • 쇠막대기는 여는 괄호로, 레이저는 1로 표현하여 연결 리스트로 저장
  • 쇠막대기에 대한 닫는 괄호가 나오면 여는 괄호가 나올 때까지 연결 리스트를 거슬러 올라가면서 레이저를 카운트

여기서 문제는 하나의 쇠막대기가 하나의 레이저를 자르는 한 번의 상호작용에 O(1)의 시간이 들어가고 있다는 점입니다. 그러면 쇠막대기의 개수도 O(N), 레이저의 개수도 O(N)이기 때문에 전체 시간복잡도는 O(N2)가 됩니다. 최악의 경우로써, N/4개의 괄호를 열고, N/4개의 레이저를 만들고, N/4개의 괄호를 닫는 입력을 생각해볼 수 있습니다.

해결책으로는, 연결 리스트 대신 스택을 사용해서 닫히지 않은 쇠막대기를 관리하고, 연결 리스트 대신 누적합(prefix sum) 배열을 사용해서 특정 쇠막대기를 절단하는 레이저의 개수를 구하면 되겠습니다.

참고로, 현재 문제는 단순하므로 굳이 이 용어를 사용할 필요는 없지만, 이러한 유형의 일반적인 테크닉을 라인 스위핑(line sweeping)이라고 합니다.

도움이 되셨기를 바랍니다!

leejun51   1년 전


byeongkeunahn님 답변 감사합니다 ㅠ

아직 실력이 부족해서 한 방향에 꽂히면 다른 방향을 못봤었는데, 

시간 복잡도로 설명주셔서 알아차릴 수 있었습니다.


감사합니다!

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