문제
세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 입력받은 rounds만큼의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성
입력
int타입의 게임 횟수 rounds
출력
ArrayList<String[ ]>타입의 rounds 결과의 모든 경우의 수
입출력 예시
ArrayList<String[]> output = rockPaperScissors(5);
System.out.println(output);
/*
[
["rock", "rock", "rock", "rock", "rock"],
["rock", "rock", , "rock", "rock", "paper"],
["rock", "rock", , "rock", "rock", "scissors"],
["rock", "rock", "rock", "paper", "rock"],
["rock", "rock", "rock", "paper", "paper"],
["rock", "rock", "rock", "paper", "scissors"],
["rock", "rock", "rock", "scissors", "rock"],
// ...etc ...
]
*/1. 문제 접근하기
순열과 조합 문제는 대부분 재귀함수를 사용한다.
가위바위보 게임에서는 각 라운드마다 '가위' '바위' '보' 중 하나를 선택하는 행위가 반복된다. 입력받은 라운드수 만큼 반복이 끝나면 게임은 종료된다.
이 과정은 재귀적 풀이에 적합하다.
2. 어떻게 풀어야 하는가?
-
문제를 가장 작은 단위로 쪼개기
- 문제는 어떤것을 반복하고 있는가?
rounds=5 : 1판 > 1판 > 1판 > 1판 > 1판 , 한 라운드에서의 선택
- 문제는 어떤것을 반복하고 있는가?
-
단순한 문제부터 해결하기 : 재귀의 기초(base case) = 종료조건
- 재귀 호출은 언제 종료되는가?
남은 라운드 수가 0일 때
- 재귀 호출은 언제 종료되는가?
-
남은 복잡한 문제 해결하기
- 그렇지 않은 경우( recursive Case ) : 라운드 수가 남은 경우
현재 라운드에서 선택을 결정하고, 다음 라운드로 이동하여 재귀를 호출하는 과정
- 그렇지 않은 경우( recursive Case ) : 라운드 수가 남은 경우
-
코드 구현을 위한 의사코드
// 0. 재귀 호출 종료 조건 설정
// 1. 선택지 'rock', 'paper', 'scissors' 를 순회하며 하나 선택
// 2. 다음 라운드로 이동하여 재귀 호출
// - 재귀 호출 시 라운드 하나씩 감소
// - 이전 라운드 선택을 기억해야함. 따라서 기억용 리스트 사용
// - 재귀 호출의 결과는 [이전 라운드 선택+다음 라운드 선택]의 경우의 수
// 3. 종료 조건 확인 및 종료 시 결과 반환💻 코드 구현
public ArrayList<String[]> rockPaperScissors(int rounds) {
ArrayList<String[]> outcomes = new ArrayList<>(); // 결과 담는 ArrayList
String[] playedSoFar = new String[rounds]; // 이전 라운드까지의 선택을 나타내는 배열
permutation(rounds, playedSoFar, outcomes); // 재귀 호출 함수
return outcomes;
}
// 재귀를 사용할 함수 permutation 생성
// rps : 가위 바위 보 선택지
// currentPlay : 현재 라운드에서의 선택
public static void permutation(int rounds, String[] playedSoFar, ArrayList<String[]> outcomes) {
// 0. 재귀 호출 종료 조건
if (rounds == 0) {
outcomes.add(playedSoFar.clone()); // 현재까지의 선택을 결과에 추가
return;
}
String[] rps = { "rock", "paper", "scissors" };
// 1. 선택지 'rock', 'paper', 'scissors' 를 순회
for (int i = 0; i < rps.length; i++) {
String currentPlay = rps[i]; // 현재 라운드 선택하기
playedSoFar[rounds-1] = currentPlay; // 현재 라운드 선택을 playedSoFar 배열에 저장
permutation(rounds-1, playedSoFar, outcomes); // 2. 다음 라운드로 이동해 재귀 호출
}
}근데 이렇게 했더니,
playedSoFar[rounds-1] = currentPlay;때문에
rounds = 5 이면 playedSoFar[4] 에 저장
rounds = 4 이면 playedSoFar[3] 에 저장
rounds = 3 이면 playedSoFar[2] 에 저장
...
출력 시 가중치 적용 정렬(Weighted Sort) 이 안된다.
레퍼런스 코드를 보니
//배열의 크기를 하나 늘리고, currentPlay를 요소로 넣어줍니다.
String[] concatArray = Arrays.copyOf(playedSoFar, playedSoFar.length + 1);
concatArray[concatArray.length - 1] = currentPlay;이런식으로 배열의 크기를 한칸씩 늘리며 복사한 뒤 차례로 저장했더라!
그래서 난,
playedSoFar[playedSoFar.length - rounds] = currentPlay;로 변경하여 해결~!
| 회고
이 문제는 오늘 배운 순열, 조합의 가장 첫 문제이다. 이걸 완전하게 이해하는데 10시간은 걸린 것 같다....
몇 줄 안되는 코드지만 중복순열의 개념, 재귀적 사고, 코드문법 등 처음 접하고 모든게 익숙하지 않은 방식이라 정말 오래 걸렸다.
- 중복 순열 문제래! 중복 순열? 그게 뭔데?
- 아 그래 중복 순열 알겠어~ 근데 그래서? 어떻게 풀어야 해? 어디서부터 접근해야해?
- 재귀로 풀어야 한다고? 재귀.... 재귀.... 재귀가 뭐 계속 반복한다는 개념이었던 것 같은데, 그래서 재귀로 뭘 어떻게 풀어야 하지? 재귀로 푼다는게 뭐였더라?ㅜㅜ
- 모르겠고, 일단 손으로 어떻게 답이 도출되는지 과정을 한번 써내려가보자.
- 그래 이렇게 경우의수가 생성이 되겠지? 이걸 재귀적 코드로 어떻게 구현해...?
- 난리 부르스를 추다가, 뭐 일단 손으로 적었을 때 대충 어떻게 돌아가는지 아니까 그럼 재귀를 푸는 방법을 알아보자! 아 재귀는 이런식으로 풀었었지~! 재귀로 푸는 단계를 천천히 이 문제에 적용해서 적어보자!
그래도 이 문제를 풀기 위해 나는 어떤 순서로 사고해야 하는지, 그저 막막한게 아니라 정확히 어떤 부분을 내가 몰라서 진행이 안되는건지 진단하며 더디지만 뎁스있게 진행해본 점이 고통스럽지만 뿌듯했다.
응... 다음 문제 주세요.....
