7469번 - K번째 수
해당 문제를 pypy3 기준으로 제출할 경우,
파이썬 내장 정렬 함수를 이용해서 너무 쉽게 풀이가 됩니다.
정렬 후에 딕셔너리를 이용해서 좌표 압축을 하고, 각 숫자가 원래 어떤 인덱스였는지를 표현해주면 풀이가 완성됩니다.
arr: 1 5 2 6 3 7 4
idx: 0 1 2 3 4 5 6
=>
arr: 1 2 3 4 5 6 7
idx: 0 2 4 6 1 3 5
위 idx를 사용해서 각 쿼리에 대해 i-1 <= idx <= j-1 를 만족하는 k번째 숫자를 for문을 이용해서 구하면 되니,
첫 정렬 시간복잡도 O(NlgN), 모든 쿼리에 대한 시간복잡도 O(NQ)를 더해주면 O(NlgN + NQ)로 pypy3에서 (python3 TLE) AC를 받게 됩니다.
https://www.acmicpc.net/source...
머지 소트를 이용하지 않고도 매우 쉽게 맞을 수 있는 문제여서 문제의 난이도를 낮추던가, pypy3의 시간을 더 팽팽하게 잡아야 하지 않을까 싶습니다. 고수님들의 의견이 궁금해요!
정해의 시간복잡도는 O(Q(logN)^2)일것 같긴 합니다시간을 줄이는게 좋아보이긴 합니다.
댓글을 작성하려면 로그인해야 합니다.
spark_1130 2년 전 1
해당 문제를 pypy3 기준으로 제출할 경우,
파이썬 내장 정렬 함수를 이용해서 너무 쉽게 풀이가 됩니다.
정렬 후에 딕셔너리를 이용해서 좌표 압축을 하고, 각 숫자가 원래 어떤 인덱스였는지를 표현해주면 풀이가 완성됩니다.
arr: 1 5 2 6 3 7 4
idx: 0 1 2 3 4 5 6
=>
arr: 1 2 3 4 5 6 7
idx: 0 2 4 6 1 3 5
위 idx를 사용해서 각 쿼리에 대해 i-1 <= idx <= j-1 를 만족하는 k번째 숫자를 for문을 이용해서 구하면 되니,
첫 정렬 시간복잡도 O(NlgN), 모든 쿼리에 대한 시간복잡도 O(NQ)를 더해주면 O(NlgN + NQ)로 pypy3에서 (python3 TLE) AC를 받게 됩니다.
https://www.acmicpc.net/source...
머지 소트를 이용하지 않고도 매우 쉽게 맞을 수 있는 문제여서 문제의 난이도를 낮추던가, pypy3의 시간을 더 팽팽하게 잡아야 하지 않을까 싶습니다. 고수님들의 의견이 궁금해요!