boompatron   9달 전

파이썬으로 풀고 있는데 계속 시간 초과가 납니다.... 접근 방식이 잘못된 걸까요??

제 풀이 방식은 우선 각 대륙 별로 테두리에 해당하는 좌표들을 coord라는 이차원 리스트에 넣은 다음 다른 대륙의 두 개의 점의 좌표를 이용해 두 좌표 사이의 거리를 계산을 해서 최솟값을 산출하는 방식인데...

시간을 줄일 수 있는 방식이 있는지, 아니면 접근이 완전을 완전히 잘못해서 다시 해야 하는지 잘 모르겠습니다...

sinsung6722   9달 전

제가 볼때는 알고리즘상의 시간 복잡도는 만족하나, 구현 과정에서 특정 라이브러리를 잘못 사용해서 문제가 된 것 같습니다.

소스코드 28번째 줄을 보면, 

'[tmp_x, tmp_y] not in coord[append_pos]:'

즉, 특정 좌표가 경계값 목록에 이미 포함되었는지 확인하는 소스코드가 있습니다.

리스트에서 in 연산자를 통해서 찾기 때문에 검색에 걸리는 시간복잡도는 리스트의 데이터 개수에 비례한 O(n) 입니다.

그리고, 이 부분을 이용해서 시간초과를 일으키는 저격 데이터를 만들 수 있습니다.

`

100

1 1 1 1 1 ...

1 0 1 0 1 ...

1 1 1 1 1 ...

0 1 0 1 0 ...

1 1 1 1 1 ...

...

`

과 같이 데이터를 생성시킬 경우, coord[append_pos]에 담기는 경계좌표는 0과 인접한 1의 개수에 비례하므로, 약 7500개가 리스트에 담기게 됩니다.

또한, in을 이용한 리스트 비교는 1이 담겨진 큐에 대해서 4방향으로 검색하므로, 약 7500*4 = 30000 번의 비교연산이 수행됩니다.

이를 곱하면 7500 * 30000 = 225000000(2억 2500만)이 되어서, 시간초과제한인 2초를 넘기기에 충분하게 됩니다.

coord에 담기는 값을 리스트가 아닌, set()으로 변경시켜보시길 바랍니다.

리스트가 아닌,  set()을 쓰면 존재여부를 확인하는데에 해시 계산시간인 c가 걸리므로, 검색을 O(1) 안에 해결할 수 있습니다.

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