글 읽기 - 7453 문제 정렬할 때 시간초과가 왜 발생하지 않는건가요?

pjy1368 4년 전 0

다양한 방법이 있겠지만, 투 포인터 알고리즘을 채택해서 푸신 분들을 보니까 A와 B의 부분합을 담은 AB배열, C와 D의 부분합을 담은 CD배열을 먼저 만들고 정렬하는 모습이 보였습니다. 그런데 AB와 CD의 사이즈는 최대 1600만 개이고, 이를 퀵 소트로 정렬한다고 하면 시간 복잡도가 1600만 x 24로 4억이 좀 안 되는 값이 나오게 됩니다. 이를 1번만 수행해도 시간 초과가 날 것 같은데 어째서 2번을 수행하고난 뒤, 투 포인터 알고리즘을 적용해도 시간초과가 나지 않는 걸까요?

sanha93 4년 전 0

퀵 소트라고 해서, 다 같은 퀵소트가 아닙니다.

어느 언어냐에 따라 다르겠지만, 그 언어의 그 버전 기준으로, 소팅은 비슷하지만 다 다릅니다.

한번 아래 블로그 봐보세요.

각 언어별, 그 언어의 함수별 + 들어있는 데이터의 종류에 따른 차이를 잘 정리 해 놓았네요

https://www.acmicpc.net/blog/view/58

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

문제

문제

출처

ICPC

7453 문제 정렬할 때 시간초과가 왜 발생하지 않는건가요?

pjy1368 4년 전 0

sanha93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말