230725 프로그래머스 삼총사 문제 풀이

230725  프로그래머스 삼총사 문제 풀이

 

문제

숫자로 배열이 주어질 때, 배열에서 3개의 원소를 조합으로 뽑아서 모두 더 했을 때 0이 되는 경우의 수 구하기

조합: array.length C 3

https://school.programmers.co.kr/learn/courses/30/lessons/131705

프로그래머스

 

조합 경우의 수 구하기

앞의 숫자보다 높은 경우만 생각-> 왜? 정렬 했을 때 모두 같기 때문

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 6가지는 모두 정렬 했을 때 [1,2,3]으로 같음.

조합에서는 순서를 고려하지 않으므로 [1,2,3]만 생각

 

 

[1,2,3,4]에서 3개 뽑는 경우의 수

순서를 고려할 경우 총 4*3*2 = 24 지만 6개씩 겹치므로 순서를 고려한 24/6 = 총 4가지

첫 번째	두 번째	세 번째
1	2	3
		4
	3	4
2	3	4

 

[1,2,3,4,5]에서 3개 뽑는 경우의 수

순서를 고려할 경우 총 5*4*3 = 60 이지만 6개씩 겹치므로 순서를 고려한 60/6 = 총 10가지

첫 번째	두 번째	세 번째	총 합
1	2	3	6
		4	7
		5	8
	3	4	8
		5	9
	4	5	10
2	3	4	9
		5	10
	4	5	11
3	4	5	12

 

for문을 3번 돌리는 것이 아닌 재귀를 통해 깊이 우선 탐색(DFS)한다

3번의 재귀를 통해 3개의 숫자를 선택하여 더한 현재 값 curSum이 0인 경우가 문제에서 제시한 경우이므로 

answer 값을 1씩 증가시킨다

function solution(number) {
  let answer = 0;
  function dfs(count,start, curSum) {
    if(count) console.log(`${"━".repeat(count-1)} ${start}번째 숫자를 더해서 현재 합: ${curSum} ${count ===3?"end":''}`)
    if (count === 3) {
      if (curSum === 0)
        answer += 1;
      return;
    }
    for (let i = start; i < number.length; i++) {
      dfs(count + 1,i + 1, curSum + number[i]);
    }
  }

  dfs(0, 0, 0);
  return answer;
}
solution([1,2,3,4,5])

dfs(count, start, curSum) 설명

count: 재귀 깊이 (=현재까지 몇개의 숫자를 선택했는가)

start: 시작할 지점 (=뽑기를 시작할 숫자 시작 지점)

curSum: 현재까지의 숫자 합(=선택한 숫자들의 합)

아래의 결과의 end부분만 보면 위의 표에서 본 10가지를 순서대로 똑같이 볼 수 있다

1번째 숫자를 더해서 현재 합: 1 
━ 2번째 숫자를 더해서 현재 합: 3 
━━ 3번째 숫자를 더해서 현재 합: 6 end
━━ 4번째 숫자를 더해서 현재 합: 7 end
━━ 5번째 숫자를 더해서 현재 합: 8 end
━ 3번째 숫자를 더해서 현재 합: 4 
━━ 4번째 숫자를 더해서 현재 합: 8 end
━━ 5번째 숫자를 더해서 현재 합: 9 end
━ 4번째 숫자를 더해서 현재 합: 5 
━━ 5번째 숫자를 더해서 현재 합: 10 end
━ 5번째 숫자를 더해서 현재 합: 6 
 2번째 숫자를 더해서 현재 합: 2 
━ 3번째 숫자를 더해서 현재 합: 5 
━━ 4번째 숫자를 더해서 현재 합: 9 end
━━ 5번째 숫자를 더해서 현재 합: 10 end
━ 4번째 숫자를 더해서 현재 합: 6 
━━ 5번째 숫자를 더해서 현재 합: 11 end
━ 5번째 숫자를 더해서 현재 합: 7 
 3번째 숫자를 더해서 현재 합: 3 
━ 4번째 숫자를 더해서 현재 합: 7 
━━ 5번째 숫자를 더해서 현재 합: 12 end
━ 5번째 숫자를 더해서 현재 합: 8 
4번째 숫자를 더해서 현재 합: 4 
━ 5번째 숫자를 더해서 현재 합: 9 
 5번째 숫자를 더해서 현재 합: 5

 

문제 풀이

입출력 예시로 테스트하기

주어진 배열이 [-3, -2, -1, 0, 1, 2, 3]일 때

1번째 숫자를 더해서 현재 합: -3 
━ 2번째 숫자를 더해서 현재 합: -5 
━━ 3번째 숫자를 더해서 현재 합: -6 end
━━ 4번째 숫자를 더해서 현재 합: -5 end
━━ 5번째 숫자를 더해서 현재 합: -4 end
━━ 6번째 숫자를 더해서 현재 합: -3 end
━━ 7번째 숫자를 더해서 현재 합: -2 end
━ 3번째 숫자를 더해서 현재 합: -4 
━━ 4번째 숫자를 더해서 현재 합: -4 end
━━ 5번째 숫자를 더해서 현재 합: -3 end
━━ 6번째 숫자를 더해서 현재 합: -2 end
━━ 7번째 숫자를 더해서 현재 합: -1 end
━ 4번째 숫자를 더해서 현재 합: -3 
━━ 5번째 숫자를 더해서 현재 합: -2 end
━━ 6번째 숫자를 더해서 현재 합: -1 end
━━ 7번째 숫자를 더해서 현재 합: 0 end
━ 5번째 숫자를 더해서 현재 합: -2 
━━ 6번째 숫자를 더해서 현재 합: 0 end
━━ 7번째 숫자를 더해서 현재 합: 1 end
━ 6번째 숫자를 더해서 현재 합: -1 
━━ 7번째 숫자를 더해서 현재 합: 2 end
━ 7번째 숫자를 더해서 현재 합: 0 
 2번째 숫자를 더해서 현재 합: -2 
━ 3번째 숫자를 더해서 현재 합: -3 
━━ 4번째 숫자를 더해서 현재 합: -3 end
━━ 5번째 숫자를 더해서 현재 합: -2 end
━━ 6번째 숫자를 더해서 현재 합: -1 end
━━ 7번째 숫자를 더해서 현재 합: 0 end
━ 4번째 숫자를 더해서 현재 합: -2 
━━ 5번째 숫자를 더해서 현재 합: -1 end
━━ 6번째 숫자를 더해서 현재 합: 0 end
━━ 7번째 숫자를 더해서 현재 합: 1 end
━ 5번째 숫자를 더해서 현재 합: -1 
━━ 6번째 숫자를 더해서 현재 합: 1 end
━━ 7번째 숫자를 더해서 현재 합: 2 end
━ 6번째 숫자를 더해서 현재 합: 0 
━━ 7번째 숫자를 더해서 현재 합: 3 end
━ 7번째 숫자를 더해서 현재 합: 1 
 3번째 숫자를 더해서 현재 합: -1 
━ 4번째 숫자를 더해서 현재 합: -1 
━━ 5번째 숫자를 더해서 현재 합: 0 end
━━ 6번째 숫자를 더해서 현재 합: 1 end
━━ 7번째 숫자를 더해서 현재 합: 2 end
━ 5번째 숫자를 더해서 현재 합: 0 
━━ 6번째 숫자를 더해서 현재 합: 2 end
━━ 7번째 숫자를 더해서 현재 합: 3 end
━ 6번째 숫자를 더해서 현재 합: 1 
━━ 7번째 숫자를 더해서 현재 합: 4 end
━ 7번째 숫자를 더해서 현재 합: 2 
 4번째 숫자를 더해서 현재 합: 0 
━ 5번째 숫자를 더해서 현재 합: 1 
━━ 6번째 숫자를 더해서 현재 합: 3 end
━━ 7번째 숫자를 더해서 현재 합: 4 end
━ 6번째 숫자를 더해서 현재 합: 2 
━━ 7번째 숫자를 더해서 현재 합: 5 end
━ 7번째 숫자를 더해서 현재 합: 3 
 5번째 숫자를 더해서 현재 합: 1 
━ 6번째 숫자를 더해서 현재 합: 3 
━━ 7번째 숫자를 더해서 현재 합: 6 end
━ 7번째 숫자를 더해서 현재 합: 4 
 6번째 숫자를 더해서 현재 합: 2 
━ 7번째 숫자를 더해서 현재 합: 5 
7번째 숫자를 더해서 현재 합: 3