[재귀] 중복 순열

박채은·2022년 11월 28일
0

코딩테스트

목록 보기
4/52

문제

[코플릿 - 가위바위보]


흐름은 동일하지만, 인자의 갯수에 따라 두 코드로 나눌 수 있다.

코드 1

  • permutation의 인자로 dept, array, result(최종 결과)가 있다.
  • dept를 -1씩 해서 dept가 0이 될 때, 재귀를 탈출한다.
    (dept가 0부터 시작하지 않아서, 인자의 갯수를 줄일 수 있다.)
public class Solution { 
	public static ArrayList<String[]> rockPaperScissors(int rounds) {
    	return permutation(rounds, new String[]{}, new ArrayList<String[]>());
	}
    
  	public static ArrayList<String[]> permutation(int dept, String[] array, ArrayList<String[]> result){
    	String[] rps = {"rock", "paper", "scissors"};
    	// 탈출 조건
    	if(dept==0){ // 하나의 경우를 완성한 경우
      		result.add(array);
      		return result; // 이전 dept의 함수가 호출된 곳으로 가야함
    	}
    	// 각 자리마다 3가지 선택지 존재(전체는 dept만큼 돌아야 하며, 그때마다 for문으로 3번의 선택을 해야함)
    	for(int i=0;i<rps.length;i++){
      		String[] newStr = Arrays.copyOf(array, array.length+1); // 배열의 크기를 늘려서 마지막에 계속 추가하기(깊은 복사)
      		// String[] newStr = array; -> "얕은 복사"(얕은 복사를 하면, 배열의 모든 원소들이 같은 주소값을 참조하여, 다 같은 값을 갖게 되기 때문에 항상 깊은 복사를 해서 배열 내의 원소들이 각기 다른 객체여야 한다.)
      		newStr[newStr.length-1] = rps[i];

      		result = permutation(dept-1, newStr, result); // permutation을 거쳐, 경우의 수들을 합침
    	}
    	return result;
  	}
}

코드 2

  • permutation의 인자로 dept, roundToGo, array, result(최종 결과)가 있다.
  • dept를 0으로 설정, roundsToGo와 같아질 때까지 1씩 추가
  • 미리 array의 크기를 지정(가위바위보는 3가지로 고정되어 있으므로) -> 코드 1과 다르게, 배열의 크기를 수동으로 늘리지 않아도 된다.
public class Solution {
    public static ArrayList<String[]> rockPaperScissors(int rounds) {
        return permutation(0, rounds, new String[rounds], new ArrayList<String[]>());
    }
    
    public static ArrayList<String[]> permutation(int dept, int roundToGo, String[] array, ArrayList<String[]> result){
        String[] rps = {"rock", "paper", "scissors"};
        if(dept==roundToGo){ // 탈출 조건
            result.add(array);
            return result;
        }
        // 재귀
        for(int i=0;i<rps.length;i++){
            String[] newStr = Arrays.copyOf(array, array.length); // 새로운 배열 생성해야함
            newStr[dept] = rps[i];

            result = permutation(dept+1, roundToGo, newStr, result);
        }
        return result;
    }
}

0개의 댓글