cuhcuh1   6년 전

80퍼센트에서 계속 시간초과에 걸립니다...

circle을 찾을 때, circle인 부분은 group이라는 값으로 채우고

circle이 아닌 부분은 -1로 채워서 중복으로 검색하는 부분을 없애 O(n)이라고 생각했는데

시간을 더 단축할 수 있는 좋은 방법이 있다면 알려주시면 감사하겠습니다 ㅠㅠ

jh05013   6년 전

rel[i]-1 not in st는 st를 차례대로 보면서 rel[i]-1과 같은지 검사하기 때문에 O(len(st))가 걸립니다.

cuhcuh1   6년 전

@jh05013

답변 갑사합니다.

저도 그 부분에서 시간이 많이 먹을 것 같아서 아래 소스와 같이 flag를 두고 접근해서 while문을 체크하는 소스도 제출해 봤지만 80퍼센트는 커녕 2퍼센트에서 시간초과로 걸리는 현상이 발생했습니다.

이건 또 왜 그런지 전혀 알 수가 없네요... ㅠㅠ

jh05013   6년 전

이번에는 flag를 만드느라 시간을 잡아먹는 것 같습니다.

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