jaboazagil   1년 전

먼저 함수 설명을 좀 해드리겠습니다.

함수는 2048게임 말판의 현재 상태를 전부 고려하지 않고, 각 말(예: 2, 4, 8, ..., 4096, ...)의 갯수만 가지고 canMove만큼 스와이프했을 때 최대 몇인 말을 가질 수 있는지를 그 말판 숫자가 가진 지수 (예: 8192인경우 2^13이므로 13 반환)로 반환하는 함수입니다.

입력 배열인 numCnt는 각 인덱스가 말의 지수(1, 2, 3...) 을 갖고 값은 그 지수에 해당하는 말의 갯수를 저장합니다.

canMove는 말판을 스와이프할 수 있는 횟수입니다.

1번 함수는 실제로 모든 말에 접근해 스와이프하는 것을 canMove횟수만큼 한 뒤 결과 배열에서 최댓값을 추출하는 방식입니다. O(20*canMove)만큼 듭니다. (최적화 시, O(canMove^2)까지 줄일 수 있습니다)

2번 함수는 2^ (현재 최댓값의 지수 + canMove) 부터 2^ (현재 최댓값의 지수 + 1)까지,  그 값이 canMove 내에 만들어질 수 있는지를 O(1)에 계산해 총 W(canMove)에 결과를 반환합니다.

이제 문제가 되는부분입니다.

시간복잡도로는 2번 함수가 더 좋아야 하는데 정작 결과는 위엣것이 324ms, 아랫것이 332ms가 나옵니다.

서버 상태가 의심되어 둘 다 다양한 시기에 3번씩이나 돌려봤는데 완전히 똑같은 결과의 반복입니다.

이유를 나름 알아보기는 했는데 저는 더 알아낼 재간이 안 되는 것 같습니다. 부디 도와주세요...

siyamaki   1년 전

프로그램의 실행시간은 일정하지 않아서  324ms 332ms정도 차이의 오차는 발생할 수 있을 것 같습니다

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