7469번 - K번째 수
아... 세그먼트 트리를 이용하면 문제를 해결할 수 있을 것으로 확신하고 도전하였으나 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 루프]가 안 끝날 수도 있는 건지 답답하네요 ㅠ
쿼리마다 노드 벡터를 통째로 복사하고 계시는데 그렇게 하면 O(lgn)이 아닐 것 같네요
아! 그렇구나.... ㅠㅠ
정말 빠르시군요
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;
댓글을 작성하려면 로그인해야 합니다.
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 루프]가 안 끝날 수도 있는 건지 답답하네요 ㅠ