[Java] 시간 초과

[백준 11279번] 에서 힙을 직접 구현해보다가 시간 초과가 된 부분이 있었다.

복잡한 조건문이 문제가 되었었다.

 

---

수정전 (오답 부분)

while (true) {
    int leftChild = parent * 2;
    int rightChild = parent * 2 + 1;

    if (index > rightChild) {
        if (array[leftChild] > array[rightChild] && compare(leftChild, parent)) {
            swap(leftChild, parent);
            parent = leftChild;
        } else if (array[rightChild] > array[leftChild] && compare(rightChild, parent)) {
            swap(rightChild, parent);
            parent = rightChild;
        }
    } else if (index > leftChild && compare(leftChild, parent)) {
        swap(leftChild, parent);
        parent = leftChild;
    } else {
        break;
    }
}

/**
boolean compare(int child, int parent) {
    if (this.array[child] > this.array[parent]) {
        return true;
    } else {
        return false;
    }
}
**/

 

---

수정후 (조건문 수정 & 함수 호출 대신 직접 비교)

while (true) {
    int leftChild = parent * 2;
    int rightChild = parent * 2 + 1;
    int largest = parent;

    if (index > leftChild && array[leftChild] > array[largest]) {
        largest = leftChild;
    }

    if (index > rightChild && array[rightChild] > array[largest]) {
        largest = rightChild;
    }

    if (largest == parent) {
        break;
    }

    swap(largest, parent);
    parent = largest;
}

 

 

최적화 방법

1. 불필요한 비교 연산을 줄인다. (한 번의 패스로 최대값 찾기)
2. 코드 복잡성을 줄이고 CPU 분기 예측이 개선되도록 한다.
3. 중첩 조건문 제거 (중첩된 if-else 구문이 깊어질수록 코드 실행 경로가 늘어나 최적화가 어려워짐.)
4. 경계 조건 확인을 명확하게 한다.
5. 함수 호출로 인한 오버헤드 제거 (스택 프레임 생성 등의 오버헤드 발생)