[프로그래머스] 연습문제 / 삼총사 / Lv1 / JS

 

---

문제 설명(Lv1 / 76% 정답률)

 

입출력 예

 

number	result
[-2, 3, 0, 2, -5]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 학생들의 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2) 이 삼총사가 될 수 있으므로, 5를 return 합니다.

입출력 예 #3

• 삼총사가 될 수 있는 방법이 없습니다.

 

나의 접근 방법

1. Number 배열에서 3개씩 뽑아서 조합 하는 함수 + 조합된 3개를 계산

2. 조합하는 함수를 헤매다가 3중 반복문으로 해결(개선이 필요하다 생각함) => 완전 탐색(Brute Force) 방법

 

나의 JS 코드 / 시간복잡도

function solution(number) {
    var answer = 0;
   
    for(let i=0; i<number.length-2; i++){
        for(let j=i+1; j<number.length -1; j++){
            for(let k=j+1; k<number.length ; k++){
                if(number[i]+number[j]+number[k] === 0 ) answer += 1;
            }
        }
    }
    return answer;
}

 

시간 복잡도

삼중 반복문을 사용하고 있으므로 시간복잡도는 **O(n³)**입니다.

• 첫 번째 반복문: n
• 두 번째 반복문: n−1
• 세 번째 반복문: n−2
• 따라서 전체 조합 수는 즉 O(n³).