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

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

프로그래머스

 

 

문제설명

 

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

 

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

 

문제 해결 방법

 

파이썬의 조합으로도 풀 수 있었지만, 백트래킹으로 문제를 풀었다. 

 

number리스트의 원소별로 학생의 번호를 달았다. 왜냐하면 문제 제한 사항에 서로 다른 학생의 정수 번호가 같을 수 있다는 문구때문이다. 예를들어 number리스트에 학생 10명이 있다고 가정했을때, 5명의 정수 번호가 0이면 학생 번호로 구분해야한다. 

 

number리스트를 방문 여부를 체크하면서 조건에 맞게 재귀 호출을 한 경우 카운트를 매기며, 총 카운트가 3이되면, 더이상 재귀 호출을 하지 않게끔 했다. 

 

카운트가 3이 됐을때, 문제의 조건(삼총사의 정수 번호 합이 0인 경우)에도 부합하면 totalResult에 삼총사를 추가한다. 

 

최종적으로 totalResult가 만들어졌으면, 중복된 요소들을 삭제하기 위해 요소들을 tuple형태로 바꾸어 주고, 리스트를 최종적으로 set() 으로 변경하기 좋은 상태를 만든다. 

 

준비가 되었으면 set()으로 변경해주면 중복 요소 처리를 할 수 있다. 

 

정리된 집합의 원소 수를 세면 그것이 정답이다. 

 

 

코드 구현

 

 

dfs를 통해 구현한 코드 

 

# 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사
def solution(number):
    answer = 0
    
    newL = []
    for idx, i in enumerate(number):
        newL.append([idx, i])
        
    totalResult = []
    
    def dfs(cnt, visited, summ, result, totalResult):
        for idx, i in enumerate(newL):
            if visited[idx] == False:
                cnt += 1
                summ += i[1]
                visited[idx] = True
                result.append(i)
                
                if cnt == 3 and summ == 0:
                    totalResult.append(result[:])
                
                if cnt < 3:
                    dfs(cnt, visited, summ, result, totalResult)
                    
                visited[idx] = False
                cnt -= 1
                summ -= i[1]
                result.pop()
                
    for idx, i in enumerate(newL):
        summ, cnt = 0, 0
        result = []
        visited = [False] * len(newL)
        visited[idx] = True
        cnt+=1
        summ+=i[1]
        result.append(i)
        dfs(cnt, visited, summ, result, totalResult)
        
    
    newS = set()
    tmpL = []
    for i in totalResult:
        tmpL = sorted(i, key = lambda x:x[0])
        tuple_arr = [tuple(i) for i in tmpL]
        newS.add(tuple(tuple_arr))
        

    answer = len(newS)
    
    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N!)

 

 

최적화 및 개선

 

재귀 함수 호출시 불필요한 매개변수를 삭제함

 

 

어려웠던 점

 

이번 문제는 진짜 어려웠다. 

특히 백트래킹을 구현할 때 계속 시간초과가 났다. 분명히 코드는 제대로 작성한것 같다고 생각했다. 

코드를 분석해보니, 문제 조건과 카운트 수가 맞아서 totalResult에 삼총사를 추가하고나서 다음 절차를 진행할 때, totalResult내부의 값이 자꾸 바뀌는 문제가 발생했다. 알아보니 리스트를 새로 만들어주지 않고 계속 똑같은 리스트가 뒤에 절차를 진행할 때도 재활용된다는 문제였다. 이를 위해서 리스트 슬라이싱을 통해 새로운 리스트를 만드는 식으로 코드를 변경했더니 문제가 해결됐다. 

 

이 이후에는 자꾸 대부분의 테스트케이스에서 시간 초과가 났다. 

진짜 분명 코드는 제대로 작성한 것 같다고 생각했다. 

 

그런데 아뿔싸 설마,,?

 

재귀 호출을 할때, 카운트 제한(3)을 조건문으로 걸어주지 않아서 시간 초과가 나는건가?

맞았다. 이때문에 불필요한 재귀 호출을 마구마구마구 하기 때문에 시간 초과가 났었다. 

해당 조건을 추가해주고 나니 더이상 시간 초과가 나지 않았다. 

 

그리고 리스트 원소를 중복제거 하기 위해서 집합자료형으로 바꾸는 과정에서 애를 먹었다. 

그냥 일반 리스트면 몰라도 이중 리스트는 쉽지 않았다!!! 내부의 내부의 리스트를 튜플로 변경시켜주고, 그것들을 감싸고있는 껍데기도 튜플로 변경시켜줘야 한다. 그러면 Hashable 자료형인 튜플로 변경할 수 있게된다..!!!!!!

 

lv1짜리 문제지만, 내가 알고있는 파이썬 문법에 구멍이 있다는 것을 크게 깨달았다. 이대로 정진!!!!!!!