Programmers 삼총사 - Python

문제 링크

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

프로그래머스

 

문제 설명

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

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

 

코드 설명

def solution(number):
    answer = 0
    result = [] // 배열 정의
    def dfs(start):
        nonlocal answer
        if len(result) == 3: // 총 3개가 모였을 때 조건 검사
            if sum(result) == 0: // 배열의 합이 0인지
                answer += 1 // 참이면 1 증가
                return // 15번째줄로 회귀
            else:
                return // 15번째줄로 회귀

        for i in range(start,len(number)): // 시작 인덱스부터 총 길이까지
            result.append(number[i]) // 하나씩 추가한 후
            dfs(i+1) // 깊이 탐색으로 다음 인덱스 추가
            result.pop() // 9, 11번째줄에서 return된 후 넣었던 값 추출
    dfs(0) // 0번째 인덱스부터 시작
    return answer

 

Level 1 문제였지만 dfs 개념이 필요해서 레벨치고 꽤 신경써야할 문제였다고 생각한다.

combination을 사용해서 3개의 값을 추출할 수도 있지만 dfs 개념으로 풀었다.

0번째 인덱스부터 시작해서 값을 하나씩 추가하고 result에 3개가 모이면 총 합이 0인지 판단한 후

참이면 answer + 1 후 return 했고 거짓이면 바로 return 했다.

return 후에 result.pop이 되면서 마지막 값을 추출 후 다음 값을 넣어준다.

 

예) 아래 숫자는 인덱스로 예를 들어보겠다.

 

0,1,2 => 총 3개가 되었으니 result의 총합 확인 => 0이면 answer + 1 -> return => 2를 제거하고 3 추가

이 메커니즘을 활용해보면

0,1,2 -> 0,1,3 -> 0,1,4 -> 0,2,3 -> 0,2,4 -> 0,3,4 -> 1,2,3 -> 1,2,4 -> 1,3,4 -> 2,3,4

총 5C2의 값 10가지 전부 순회한다.