SW Expert Academy 5648 "원자 소멸 시뮬레이션"

방법1

전체 원자들을 감싸는 enclosing box의 max(가로, 세로)초 동안의 모든 움직임을 추적한다.

원자가 중간에 enclosing box의 밖으로 나가면 소멸처리.

같은 시각에 같은 지점에 2개 이상의 원자가 모이는 것이 검출되면 방출 에너지를 구해 답에 누적한다.

괜찮은 구현인 줄 알았는데 제한시간에 아슬아슬하게 걸침. 각 시각마다 정렬하는 것 때문일까?

좌표의 최대 범위를 W라 하면 시간복잡도는 O(W * N * lg N)

방법2

각 원자에 대해 그 원자와 충돌할 수 있는 원자가 있을 수 있는 위치를 미리 검사.

가까이 있는 원자와 먼저 충돌하기 때문에 충돌 소요시간이 작은 것부터 검사한다. 이 문제에선 원자가 상하좌우로만 움직이므로 최대 3개의 위치만 보면 됨. 근데 1.7초나 걸렸나 상수가 큰가보다.

시간복잡도는 O(W * N)

방법3: 더 빠른 사람들의 코드

방법2에서 더 발전한 방법. 위에서 좁은 범위부터 검사한다고 했는데 방법2의 시간복잡도 중 W는 여기서 나온 것이다. 가정할 충돌 소요시간을 1씩 증가시켜가며 검사하기 때문에 불필요한 값에 대해서도 검사한다.

방법3는 모든 충돌 가능성이 있는 모든 원자쌍 사이의 충돌 소요시간, 그 원자쌍의 정보의 리스트를 만들어 충돌 소요시간이 작은 것부터 정렬을 한다. 이렇게 하면 반드시 존재하는 충돌 소요시간에 대해서만 보게 된다.

시간복잡도는 O(N^2)