[프로그래머스 JS] 삼총사

📖 문제 설명

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다.

 

예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

 

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

---

🚫 제한 사항

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

---

💾 입출력 예시

 

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

 

---

⌨️ 나의 풀이 (코드)

 

먼저 의사 코드를 작성했다.

 

1. 배열을 순회하며 각 요소로 만들 수 있는 삼총사 조합이 있는지 확인
2. 만약 이미 만들어진 조합(같은 인덱스 번호)라면 제외

 

논리 구조 자체는 쉬웠는데, i, j, k를 3번 연속 사용한 반복 루프는 시간 복잡도가 높아지고 효율적이지 못한 코드라고 생각해 좀 더 효율적인 방법을 생각해 보았다.

 

이 과정에서 백트래킹이라는 풀이 방식을 알게 되었다.

 

백트래킹이란, 재귀를 통해 진행하며 탐색 과정에서 성공 가능성이 없어진 탐색 경로(루트)는 제외하는 알고리즘 풀이법이다.

 

재귀를 활용한 백트래킹의 의사 코드는 다음과 같이 쓸 수 있다.

 

void findSolutions(n, other params) :
    if (found a solution) :
        solutionsFound = solutionsFound + 1;
        displaySolution();
        if (solutionsFound >= solutionTarget) : 
            System.exit(0);
        return

    for (val = first to last) :
        if (isValid(val, n)) :
            applyValue(val, n);
            findSolutions(n+1, other params);
            removeValue(val, n);

 

이를 기반으로 실제 코드를 구현해보면 다음과 같다.

 

function solution(number) {
  let tmCount = 0;

  const recursiveFunc = (acc, cur) => {
    if (acc.length === 3) {
      tmCount += acc.reduce((a, b) => a + b) ? 0 : 1;
      return;
    }

    for (let i = cur; i < number.length; i++) {
      recursiveFunc([...acc, number[i]], i + 1);
    }
  };

  recursiveFunc([], 0);

  return tmCount;
}

 

위 코드를 온전히 직접 구현했다면 참 좋았겠지만...아쉽게도 아니다.

 

해당 코드는 Collection50 , 유영준 , SangJin , yelinz515 외 46 명이 작성한 프로그래머스 풀이와 같다.