ghw0926   3년 전

안녕하세요.

혼자 풀어보려다 도저히 접근이 어려워 해당 알고리즘을 확인하여 아래와 같이 중간 만나기 알고리즘을 통해 해결하려했습니다.

풀이를 순서대로 나열하자면

1) a, b배열을 합하고, c, d배열을 합하여 두개의 배열을 만듦

2) 만든 두 배열을 sort를 통해 정렬

3) 중간에서 만나기 알고리즘을 통해 합을 확인

위 풀이에서 n을 최악의 경우인 4000으로 잡고 시간복잡도를 계산하면

1) 4000 * 4000 = 16_000_000

2) 4000 * log4000 + 4000 * log4000 = 약 28_800

3) 최악 8000

위 과정을 더해봐야 결국 16_036_800으로 1.6 * 10^7 언저리인데

시간 제한이 12초인 상황에서 왜 시간초과가 발생하는지 납득이 안가네요.

다른 방식으로 해결한 현재는 sort 과정의 nlogn이 문제가 된다고 의심은 가긴하는데 확신은 안드네요.

제 시간복잡도 계산이 잘못됐을까요? 아니면 12초가 1.6 * 10^7 계산을 허용하지 못할만큼의 시간대일까요?

아니면 Node.js라서..?

읽어주셔서 감사합니다.

verandaaa   3년 전

혹시나 node.js로 푸시는 분들 있으시면 보실까봐 댓글 남깁니다

투포인터 방법으로 node.js 절대로 통과가 안돼서 java로 문법만 바꿔서 그대로 넣었더니 통과 되더라구요...

반대로 map을 사용한 방법은 java는 통과가 안되는데 node.js는 통과가 되구요 

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