[프로그래머스]삼총사 - 파이썬

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

문제설명:

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 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

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

입출력 예 #3

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

문제 풀이

문제가 점점 어려워져 머릿속에서만 알고리즘을 생각하고 구현하는 데에 한계가 생겼다. 그래서 앞으로는 수도코드를 작성해 문제를 해결하기로 했다.

☝🏻 먼저 이 문제의 핵심은 3 개의 합이 0 이 되는 조합을 어떻게 만드냐는 것.

가장 먼저 생각 난 것은 for 문 3 개를 써서 조합을 찾는 것

수도코드:

    for i in range(len(number)):
        for j in range(1, len(number)):
            for k in range(2, len(number)):
                각 인덱스 위치의 숫자를 모두 더했을 때 0 이면:
                    각 인덱스 위치의 수를 하나의 리스트로 만들어 result 에 append

• 가장 바깥의 for 문의 i → 0 부터 시작
• 그 다음 for 문의 j → 1 부터 시작
• 가장 안 쪽의 for 문 k → 2 부터 시작
• 이렇게 result 에 추가된 리스트를 중복을 없애기 위해 set(result) 하면 될 거라 생각헀는데, 결과를 set으로 만들 때, 리스트는 해시 불가능하여 TypeError가 발생했다.
  

그래서 루프 인덱스 시작을 위에처럼 하는게 아니라 i+1, j+1 로 하면 중복 없이 바로 구할 수 있는거 아닌가?

    for i in range(len(number)):
        for j in range(i+1, len(number)):
            for k in range(j+1, len(number)):
                각 인덱스 위치의 숫자를 모두 더했을 때 0 이면:
                    각 인덱스 위치의 수를 하나의 리스트로 만들어 result 에 append

number = [-2, 3, 0, 2, -5] 라면

• i = 0 일 때: j = 1, k = 2
  • [-2, 3, 0]
  • [-2, 3, 2]
  • [-2, 3, -5]
• i = 0 일 때: j = 2, k = 3
  • [-2, 0, 2]
  • [-2, 0, -5]
  • [-2, 2, -5]
• i = 1 일 때: j = 2, k = 3
  • [3, 0, 2]
  • [3, 0, -5]
• i = 1 일 때: j = 3, k = 4
  • [3, 2, -5]
• i = 2 일 때: j = 3, k = 4
  • [0, 2, -5]

위 조합 중 합이 0 이 되는 갯수는 2개로 정답!

최종코드

def solution(number):
    result = []

    for i in range(len(number)):
        for j in range(i+1, len(number)):
            for k in range(j+1, len(number)):
                if number[i] + number[j] + number[k] == 0:
                    result.append([number[i], number[j], number[k]])

    return len(result)