[프로그래머스] 레벨1 삼총사

https://school.programmers.co.kr/learn/courses/30/lessons/131705?language=java# 

프로그래머스

 

이 문제는 조합을 활용한 문제이다. 일단 조합과 순열의 가장 큰 차이는 순서가 결과값에 영향을 주는지의 여부인데 이 문제에서는 순서를 바꾸어도 전체 합이 바뀌지 않기 때문에 조합의 개념을 적용하면 되고, 또 중복도 허용하지 않는 일반적인 조합 문제였다.

 

1. 입력값과 활용 변수에 대한 선언 및 전처리

2. 재귀 함수를 활용한 조합의 전체 가짓수 생성

  2-1. 삼총사이므로 ArrayList로 선언한 list의 사이즈가 3일때 base condition을 만들어 무조건 리턴한다.

  2-2. 이 때, list의 합들이 3이면 조건을 만족하므로 결과변수 cnt에 +1 해준다.

  2-3. 중복을 허용하지 않으므로, visit 배열을 활용해 list에 현재 없는 값들만 넣어준다.

  2-4. 추가적으로 조합이기 때문에 이미 체크한 값은 다시 체크하지 않아도 되므로 반복문의 인덱스에 활용할 변수 index를 통해 시작 범위를 제한해준다.

 

---

문제 및 입출력

---

코드

import java.util.ArrayList;

class Solution
{
    static int cnt = 0;
    
    public static void make(int[] number, ArrayList<Integer> list, boolean[] visit, int max, int index)
    {
        if(list.size()==max)
        {
            int temp = 0;
            
            for(Integer i : list)
            {
                temp += i;
            }
            if(temp==0)
            {
                cnt++;
            }
            
            return;
        }
        
        for(int i=index; i<number.length; i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                list.add(number[i]);
                make(number, list, visit, max, i);
                list.remove(list.size()-1);
                visit[i] = false;
            }
        }
    }
    public int solution(int[] number)
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        boolean[] visit = new boolean[number.length];
        make(number, list, visit, 3, 0);
        
        return cnt;
    }
}