ttobogims   10달 전

 배열 크기가 5이고, 배열값이 만약에
1 3 0 2 4 이렇게 있어요.
 각 인덱스 위치에서 자기오른쪽에 자기보다 작은게 몇 개인지 카운팅하려면 어떻게 해야할까요??
1 : 3 0 2 4 중 0(1개)
3 : 0 2 4 중 0,2(2개)
0 : 2 4 (0개)
2 : 4 (0개)

정답 : 총3개

이렇게 하려니 데이터 갯수가 많아지면 시간이 많이 걸리던데... 다른 방법 있으면 가르쳐주세요~~ㅠ

indioindio   10달 전

트리구조를 사용하시면 될 것 같네요
5 1 3 0 2 4 가 있으면 오른쪽에서 부터 트리를 만듭니다.
만들 때, 자식이 왼쪽으로 갈 때마다 부모노드의 값을 +1을 해줍니다(자기보다 왼쪽에 있는, 자기보다 작은 값들의 수). 그러다가 자식이 오른쪽으로 가게 되면, 그 노드는 부모의 노드에 저장된 값 + 1(부모가 자기보다 작으므로) 만큼 자기 오른쪽에 자기보다 작은 원소를 갖고 있습니다.
 4 ->        4 (1)           ->             4(2)             ->                  4(3)                        ->            4(4)         ->      4(4)
            2                             2 (1)                                   2(1)                                        2(2)                   (생략)    5:(0, 4+1) 개
                                         0                                      0          3 : (0, (1 + 1 개))         0(0)    3 
                                                                                                                                         1(0+1)

indioindio   10달 전

http://stackoverflow.com/questions/9495843/given-a...

이 링크를 참조하시면 구현도 나와있네요

댓글을 작성하려면 로그인해야 합니다.