Java
[Java] 시간 초과
bornsoon
2025. 5. 3. 22:16
[백준 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. 함수 호출로 인한 오버헤드 제거 (스택 프레임 생성 등의 오버헤드 발생)
728x90