자답합니다.
위 코드에서 샘플링 방법을 바꾸고(기존 O(N^2) → O(N)), 최소/최대 세그먼트 트리를 각각 나눠서 표기하면
파이썬으로 충분히 시간 안에 통과가 됩니다.
1. 샘플링 타임 O(N^2) → O(N)으로 변경 시, 7%에서 TLE 해결되나, 14% 수준에서 TLE 발생합니다
2. 각 노드를 최소/최대로 표현하는 것을 최소 트리, 최대 트리를 만들어서 표기할 경우 TLE 해결됩니다.
5817번 - 고통받는 난쟁이들
자답합니다.
위 코드에서 샘플링 방법을 바꾸고(기존 O(N^2) → O(N)), 최소/최대 세그먼트 트리를 각각 나눠서 표기하면
파이썬으로 충분히 시간 안에 통과가 됩니다.
1. 샘플링 타임 O(N^2) → O(N)으로 변경 시, 7%에서 TLE 해결되나, 14% 수준에서 TLE 발생합니다
2. 각 노드를 최소/최대로 표현하는 것을 최소 트리, 최대 트리를 만들어서 표기할 경우 TLE 해결됩니다.
댓글을 작성하려면 로그인해야 합니다.
chickenchickenlove 5년 전
파이썬 시간 제한이 너무 빡빡한 것 같습니다.
시간제한 상향 검토 부탁드립니다. 풀이방식은 아래와 같으며, 시간복잡도 O(Mlogn)입니다.
n,m는 각각 200,000으로 시간초과가 나면 안되는데 7%에서 시간초과가 발생합니다. 파이썬 제출된 풀이가 모두 시간초과인 것으로 보아, 파이썬 TLE가 과하지 않나 싶습니다.
1. 세그먼트 트리의 인덱스는 각 난쟁이의 키로 설정
2. 세그먼트 트리 노드는 2개 값을 가지고 있으며, 0번 인덱스 값은 해당 노드가 가리키는 난쟁이 키 구간의 제일 왼쪽값, 1번 인덱스 값은 해당 노드가 가리키는 난쟁이 키 구간의 제일 오른쪽값을 나타냄
(1번 예시로 들 경우, 세그먼트 트리 초기화 시 2번 노드는 키가 1~4인 난쟁이가 서있는 구간을 나타내며 [0,3] 구간을 나타내게 됨.
3. 업데이트 시, 배열에서 자리를 바꿔주고(O(2)), 세그먼트 트리에 각각 업데이트(O(2logn))이 필요함
4. 쿼리는 구간 쿼리로 O(logn) 소요됨.
5. 정답 판단은 현재 난쟁이 키의 구간의 총 길이와 난쟁이 키가 같은지 확인하는 방식으로 해결됨
아래 풀이는 최소, 최대 세그먼트 트리를 구현해서 값을 구한 것인데,
위의 제가 한 풀이는 최소, 최대 세그먼트 트리를 하나로 합쳐서 각 노드가 최소/최대를 살펴보게 한 풀이입니다.
https://jaimemin.tistory.com/1...