[프로그래머스] 삼총사

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

프로그래머스

블로그에 작성했던 멱집합 알고리즘을 응용해 풀었다. 

 

[코드 해석]

- 배열 numbers의 첫번째 요소가 포함되는 경우, 포함되지 않는 경우로 나누어 재귀를 실행

- 학생 3명만 선택되어야 하기때문에 기저케이스로 포함된 학생의 수를 나타내는 count변수가 3일경우

  합을 구해 0이 나오는지 확인 true=answer증가, false=그냥 종료시킴.

- 재귀될 때 마다 numbers의 인덱스값과, 포함된 요소에 따라 count, answer변수가 달라지지만

  매개변수를 최대한 줄이기 위해 클래스 변수로 뺐다.

Ver.1

class Solution {
    static int count = 0;     // 포함 여부 3개 제한하는 변수
    static int answer = 0;    //삼총사 개수
    static boolean[] include; //포함 여부  true = 포함, false = 미포함.
    static int[]     numbers;
    
    public int solution(int[] number) {
        include = new boolean[number.length];
        numbers = number;
        three(0);
        return answer;
    }//solution
    
    public static void three(int k){
       if(count == 3) {
			if(sum() == 0) answer++;
			return;
		}else if(k==numbers.length) return;
		else {
			count+=1;
			include[k]=true;
			three(k+1);
			
			count-=1;
			include[k]=false;
			three(k+1);
		}
    }// three
    
    static int sum() {
		int sum = 0;
        
		for(int i=0; i<numbers.length; i++) {
			if(include[i]==true) { 
				sum += numbers[i];
			}
		}
        
		return sum;
	}//sum
    
}//class

[개선할 점]

1. 조건: 부분집합 중 요소가 3개 + 요소들의 합이 0인 집합

    위 조건을 만족시키는 집합의 개수만 구하면 됨.

    그런 집합을 출력하는 거라면 include[ ]이 필요한 경우가 아니니

    include[ ]을 없애도 문제가 없을 것.

 

2. sum( )메서드 또한 없어도 됨.

    요소가 포함할 경우   >   sum += numbers[k];

    요소가 포함되지 않을 경우 >  sum -=numbers[k];       //위에서 더했기때문에 원상복귀시킴

 

3.  base case설정 시

     1) 포함된 요소개수가 3인 경우

     2) numbers의 인덱스 k가 배열의 범위를 넘지 않을 것.

    이었다.

    2)의 경우 따로 실행시킬 액션이 없고 바로 종료 return되므로

  재귀되는 블록 else { ... }의 조건식을 달아 else if ( k < numbers.length ) 으로 변경하면 코드가 더 간결해 졌을 것 같다.  

 

    Ver.2 

class Solution {
    static int count = 0;     // 포함 여부 3개로 제한하는 변수
    static int answer = 0;    // 합이 0이되는 집합 개수
    static int sum = 0;       // 합
    static int[]     numbers;
    
    
    public int solution(int[] number) {
        numbers = number;
        three(0);
        return answer;
    }//solution
    
    public static void three(int k){
       if(count == 3) {
			if(sum == 0) answer++;
			return;
		}else if(k < numbers.length){
			count+=1;
			sum+=numbers[k];
			three(k+1);
			
			count-=1;
			sum-=numbers[k];
			three(k+1);
		}
    }// three
    
}//class