jth403   2년 전

최대 힙, 최소 힙 2개를 만들고 입력값은 상대방의 인덱스를 기억합니다.

삭제 시 남아있는 상대방 인덱스를 -1로 바꾸어 실제하는 값인지 판단합니다.

게시판에 있는 반례 다 돌리면서 고쳤는데 3%에서 넘어가질 않습니다.

잘 부탁드립니다.

adfsfsf   2년 전

삽입 함수가 이상하네요. 삽입을 할 때는 이렇게 하셔야 할 것 같습니다.

1. maxHeap을 정렬합니다.

2. 이후, minHeap에서의 인덱스를 이용해 정렬 후의 인덱스를 새로 넣어줍니다.

3. minHeap쪽에서도 마찬가지로 정렬 후 maxHeap쪽의 인덱스를 바꿔줍니다.

정렬을 하면 힙 내부에서의 위치가 바뀌는데 이걸 갱신하시지 않아서 생긴 문제인 것 같네요.

adfsfsf   2년 전

예시를 적어드리겠습니다. 코드에서 순서대로 하면 아래와 같이 됩니다.

1 삽입

max [1,0]

min [1,0]

3 삽입

max [3,1], [1,0]

min [1,0], [3,1]

적으신 코드를 기준으로 하였습니다. 이 경우는 max힙이 정렬되면서 1과 3의 위치가 바뀌었음에도 불구하고 min힙의 인덱스 정보를 수정하지 않아서 생긴 겁니다. 즉, max힙에서 3이 0번에 있음에도 min힙에선 max힙의 1번 위치에 3이 있다고 판단하게 되는 겁니다.

jth403   2년 전

답변 감사드립니다.

기존의 코드도 정렬에 따른 위치변화를 상대방의 인덱스에 반영해주고있습니다.

adfsfsf   2년 전

새로 올려주신 코드로 보니까 이상한 부분을 찾을 수 있었습니다. 함수 코드 기준, 17, 18, 20, 23의 4개 줄에서 i를 j로 바꿔주셔야 할 것 같습니다.

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