n개를 입력받으면

2n개를 동적할당 해주고

오름차순으로 정렬한 다음

앞의 두개의 합을 배열의 (n+k)-1인덱스에 넣어주고

그 두개를 제외한 것들과 그 두개의 합만 다시 오름차순으로 정렬하고.. 하는식으로 해서

섞는 수를 구했습니다.

처음엔 n개

그다음엔 n-1개

...

for문안에선 이런식으로 정렬합니다.

그런데 시간초과가 나서 난감합니다..

다른 자료구조나 알고리즘을 사용해야 하나요...?

pichulia   2년 전

이런 경우엔 다른 자료구조를 사용해야겠네요....

std::priority_queue 에 대해 검색해보시길

appa   2년 전

말씀하신 알고리즘 시간복잡도를 분석해보면 O(N^2 log N)가 나옵니다. (2개를 선택하는 게 N-1번, 정렬하는데 N log N. N이 1씩 줄어든다하더라도 중간값 N/2를 잡고 시간복잡도 계산을 하면 N^2 log N이 나오죠)

힙이나 우선순위 큐, binary indexed tree 등의 자료구조를 활용할 수 있습니다.

감사합니다.

덕분에 우선순위큐를 이용해 풀었습니다.!!

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