문제 소개
풀이
public class Pr131705 {
public int solution(int[] number) {
int answer = 0;
for(int i = 0; i < number.length-2; i++) {
for(int j = i+1; j < number.length-1; j++) {
for(int k = j+1; k < number.length; k++) {
if(number[i] + number[j] + number[k] == 0) {
answer ++;
}
}
}
}
return answer;
}
}
- 문제는 Bruteforce를 이용해서 풀어보았다.
i, j, k를 통해 각 숫자를 골라 모든 경우의 수를 둘러볼 수 있는 3중 for문을 선택하게 되었다.- 문제는 풀었지만, 문득 처음에 생각났던 방식은 DFS 였기에 다른 방식의 구현이 더 좋을 수도 있지 않을까 라는 생각이 문득 들었고, 테스트를 해보았다.
- 왼쪽은 DFS, 오른쪽은 Bruteforce를 이용한 코드의 실행결과이다.
- 결과는 큰 차이는 없었지만 전체적으로 Brute force가 더 좋은 성능을 보였다.
- 이는 number 길이 제한이 매우 짧아서 그랬던 것이라 생각이 들어 길이를 1000까지 늘려 추가로 실험해보았다.
- 실행 결과는 DFS는 56초, Brute force는 0.2 초로 상당히 많은 차이가 있음을 알게 되었다.
- 이는 3중 for문으로 구현한 방식과 재귀를 통해 구현한 방식에 차이가 있었다는 것을 알게되었고, 항상 완전탐색보다 DFS가 좋은 건 아니라는 것을 제대로 느끼게 되었다.
