leejk9592   7년 전

아... 세그먼트 트리를 이용하면 문제를 해결할 수 있을 것으로 확신하고 도전하였으나 7번 넘게 시간초과가 나버렸습니다.

20%에서 6번, 80%에서 한 번 시간초과가 났습니다. 제 생각에 80%는 테스트 케이스를 랜덤으로 역순으로 채점해서 그런거 같고


제 알고리즘 방식을 간단히 소개해드리자면


1. n개의 수를 입력 받는다 -> inputs

2. 입력된 수는 겹치지 않으므로 1 ~ n 으로 압축한다 -> sorted => link => compressed

3. 압축된 수들을 이용해 각 노드 마다, 구간의 정렬된 배열을 갖는 세그먼트 트리를 만든다 => build

4. m개의 (i, j, k)를 한 줄 씩 입력 받을 때 마다 아래의 알고리즘을 실행해 정답을 출력한다

<알고리즘>

(1)  i, j 구간에 해당하는 세그먼트 트리의 노드 배열들을 가져온다 => query

(2) left : 1, right : n 을 시작으로 mid = (left + right)/2 값으로 (1)에서 가져온 배열들에 lower_bound가 몇 인지 구한다

 * 이 때, 해당 값이 배열에 포함되는지 확인하기 위해 binary_search의 결과가 true인지도 확인한다.

(3) 각 배열 들의 lower_bound 합이 k - 1이고, binary_search 결과가 한 번이라도 true 였다면 m을 반환한다.


<초기화 시간복잡도>

1. 입력 : O(n)

2. 정렬 : O(n log n)

3. 압축 : O(n log n) - STL map을 이용

4. 시행 : O(m * F(i, j, k))


<알고리즘 - F(i, j, k) 시간복잡도>

(1) 노드 배열 갖고 오기 : O( (log n)^2 )

(2) 이분탐색 이용 값 확인 : O( 2 * (log n)^3 )


결과적으로 O(n log n) + O(m (log n)^3) 라고 생각하는데...

고칠 점이 보이시면 댓글을 달아주시면 감사하겠습니다.


P.S - map을 사용하지 않고 입력된 값들의 범위를 압축을 할 수 있으면 시간을 많이 줄여 통과될 것 같기도 하고,

아니면 혹시 [algorithm 함수에서 이분 탐색 while 루프]가 안 끝날 수도 있는 건지 답답하네요 ㅠ

koosaga   7년 전

쿼리마다 노드 벡터를 통째로 복사하고 계시는데 그렇게 하면 O(lgn)이 아닐 것 같네요

leejk9592   7년 전

아! 그렇구나.... ㅠㅠ

정말 빠르시군요

leejk9592   7년 전

koosaga 님께서 얘기해주신 문제도 문제였지만

Example)

1 3

1 2 3

2 3 2

에서 이분탐색 while문이 무한루프가 도는 것을 발견하고 수정하였습니다...

위의 if ~ else ~ 문을 아래와 같이 수정하니 해결되었습니다...        

if( low <= k - 1)

        l = (l == m) ? m + 1 : m;

else

        r = (r == m) ? m - 1 : m;


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