마지막에 O(N) 풀이법이 있는 것 같네요.

https://pgr21.com/pb/pb.php?id...

@thexl

감사합니다.

deque를 이용한 O(N) 풀이법이 있다는 것을 알고는 있는데

해당 문제는 NlgN을 이용한 세그먼트 트리가 불가능한건지,

혹은 제가 문제를 아예 잘못이해하고 있는지 궁금합니다.

5백만 개의 입출력은 그 자체로 시간이 많이 걸립니다. 수 정렬하기 3 문제랑도 비교해볼 수 있는데, 최대 5자리의 수 천만개를 입력받고 O (N) 시간에 정렬하여 다시 출력하는데 2초가 넘게 소요됩니다. 여기서 시간을 대부분 소모하는 건 입출력입니다. 그렇기 때문에 이 문제에서도 3초라는 시간이 N lg N을 통과시켜주기 위해 있는 게 아닙니다. 설령 각 연산이 아주 가볍더라도 기본적으로 1억 정도가 되기 때문에 어렵습니다.

@djm03178

이해됬습니다. 감사합니다 좋은하루되세요~

세그먼트 트리로도 풀립니다. 다만 입출력에서 scanf를 쓰거나 ios::sync_with_stdin(false); 구문을 쓴 상태에서 cin을 사용해야 할 듯요.

세그먼트 트리 문제로 분류되어 있는데 안풀리면 이상하긴하죠!

@gjs001

입출력 모두 printf, scanf사용하는데 시간초과가 뜹니다ㅜ

세그먼트트리의 구현에서 잘못된것 같습니다..

@onlyhim

세그먼트 트리 초기화 할 때 혹시 무한대 값을 모든 트리 노드에다가 다 넣어주시나요? 아마 이러면 시간초과 날 듯 합니다.

저는 마지막 리프 노드 +1에다가만 무한대 값 넣어줬어요. 마지막 리프노드가 오른쪽에서 끝나면 어차피 안쓰일거고 왼쪽에서 쓰일 경우만 잘 거르게요.