1572번 - 중앙값
모든 분들 수고가 많으십니다.
1572번 문제를 몇일째 시도하다가 계속되는 시간초과에 조언을 청해봅니다.
펜윅트리로 구현했고, 여러 정답자 분들의 코드를 참고해서 작성했습니다.
오프라인에서, 10만개짜리 큰 테스트케이스를 만들어 테스트해보았는데 0.2초내로 동작하는데 온라인 제출시 시간초과가 되네요.
도움 부탁드리겠습니다. 감사합니다.
자답입니다.
입력되는 숫자범위가 0~65536 이므로, 펜윈트리에 빈도수 저장시 인덱스1번 부터 사용하기 위해서는
idx++ 을 해주어야 하는데 누락되어 있었네요. 역시나 문제조건부터 정확히 파악하여야 할 것 같습니다.
update() / getSum()에 모두 idx++ 적용하니 정답처리 되었네요.
필요하신분 아래 코드 참고하세요.
댓글을 작성하려면 로그인해야 합니다.
daniel00 6년 전
모든 분들 수고가 많으십니다.
1572번 문제를 몇일째 시도하다가 계속되는 시간초과에 조언을 청해봅니다.
펜윅트리로 구현했고, 여러 정답자 분들의 코드를 참고해서 작성했습니다.
오프라인에서, 10만개짜리 큰 테스트케이스를 만들어 테스트해보았는데 0.2초내로 동작하는데 온라인 제출시 시간초과가 되네요.
도움 부탁드리겠습니다. 감사합니다.