Cos Pro 1급 - 샘플 문제 풀이 4차 8번 (숫자카드 조합하기-재귀함수)

문제 지문 #8

1 이상 9 이하 숫자가 적힌 카드를 이어 붙여 숫자를 만들었습니다. 이때, 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 구하려 합니다.
예를 들어, 숫자 카드 1, 2, 1, 3로 만들 수 있는 수를 작은 순으로 나열하면 [1123, 1132, 1213, 1231, 1312, ... , 3121, 3211]입니다. n이 1312라면, 숫자 카드를 조합해 만든 수 중 n은 n은 5번째로 작은 수입니다.
숫자 카드를 담은 배열 card, 수 n이 매개변수로 주어질 때 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 하도록 solution 메서드를 완성해주세요.

---

#####매개변수 설명

카드에 적힌 숫자를 담은 배열 card, 수 n이 solution 메소드의 매개변수로 주어집니다.

• card는 길이가 9 이하인 배열입니다.
• card의 원소는 1 이상 9 이하인 자연수입니다.
• n은 999,999,999 이하인 자연수입니다.
• n의 자릿수는 배열 card의 길이와 같습니다.
• n의 각 자리의 숫자는 1 이상 9 이하입니다.

---

#####return 값 설명

숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 해주세요.

• 만약, n을 만들 수 없다면 -1을 return 해주세요.

---

#####예시

card	n	return
[1, 2, 1, 3]	1312	5
[1, 1, 1, 2]	1122	-1

#####예시 설명

예시 #1
앞서 설명한 예와 같습니다.
예시 #2
숫자 카드를 조합하면 [1112, 1121, 1211, 2111]를 만들 수 있습니다. 따라서 1122는 만들 수 없습니다.

728x90

혼자 풀이

함수 전체 완성하는 문제입니다. 재귀함수를 사용해야 하는 문제이고, 샘플 문제 전체에서 난이도가 가장 높은 문제입니다. 이 문제를 풀기 위해 공부를 꽤 많이 했습니다. (사실 정답을 많이 커닝했습니다)
재귀함수에 대한 이해를 돕기 위해 추가 포스팅을 작성했습니다. 참고하시면 좋겠습니다.
2022.11.04 - [Programming/Java] - [Java] 재귀함수 작성 방법 - 예제와 고려사항

[Java] 재귀함수 작성 방법 - 예제와 고려사항

한번 사용한 숫자는 다시 쓸 수 없지만, 주어지는 배열에 숫자의 중복이 가능하기 때문에 주어진 숫자를 관리하는 별도의 배열 cardCnt[10]가 필요합니다.
첫 번째 주어지는 배열인 { 1, 2, 1, 3 }을 cardCnt[10]에 넣으면 아래와 같이 만들어집니다.

0	1	2	3	4	5	6	7	8	9
0	2	1	1	0	0	0	0	0	0

다음으로 같은 크기의 curCnt[10]을 만들고 재귀호출에 따라 curCnt[10]의 값을 변경 시키면서 수를 생성합니다.
첫번째 숫자인 1123을 만드는 과정은 다음과 같습니다.

1	1	2	3	4	5	6	7	8	9
	1	0	0	0	0	0	0	0	0

11	1	2	3	4	5	6	7	8	9
	2	0	0	0	0	0	0	0	0

112	1	2	3	4	5	6	7	8	9
	2	1	0	0	0	0	0	0	0

1123	1	2	3	4	5	6	7	8	9
	2	1	1	0	0	0	0	0	0

마지막 까지 오게 되면 재귀함수를 종료하고 numList에 만들어진 수를 add합니다. 나머지는 for문을 돌면서 추가로 numList에 추가합니다.
나머지 부분도 이해를 돕기 위해 주석을 빼곡히 달았습니다.

import java.util.ArrayList;

class Solution {

    //생성한 수를 담을 전역변수 생성
    ArrayList<Integer> numList = new ArrayList<>();
    //수를 생성하는 함수 작성
    //cardCnt: 각 수의 개수
    //curCnt: 사용한 수의 개수
    //lev: 몇 자리까지 했는지를 나타내는 수
    //num: 현재 생성한 수
    public void makeNum(int[] cardCnt, int[] curCnt, int lev,int num){
        //System.out.println(lev+":"+num);
        if(lev==0){  //기저사례는 1의 자리 밑일때
            numList.add(num); //현재 생성한 수를 numList에 저장한다
            return ;
        }
        for(int i=1;i<10;i++){   //1~9까지 숫자별로 돌아가면서 
            if(curCnt[i]<cardCnt[i]){ //cardCnt의 각 숫자 개수 내에서 수를 조합한다.
                curCnt[i]++; //수를 사용했으면 증가시킨다.
//              num=num*10+i;  //num 자체를 변경해 버리면 for문의 다음 루프에 영향을 주므로 재귀함수의 입력값에 변경을 주면 안됨
                makeNum(cardCnt ,curCnt,lev-1,num*10+i); //lev에서 1을 빼서 재귀함수가 무한호출되지않도록 하고 num의 값을 전달한다.
                curCnt[i]--;//재귀함수에서 빠져나오면 들어가기전에 변경했던 값을 원복함
            }

        }
    }
    public int solution(int[] card, int n) {
        // 여기에 코드를 작성해주세요.
        int answer = 0;
        //주어진 숫자배열의 숫자를 한번씩만 사용해야 하므로 각 숫자의 개수를 관리하는 배열이 필요함
        //n은 1~9까지의 숫자가 가능 하므로 크기 10인 배열을 만들어서 1~9까지 숫자의 갯수를 관리
        int[] cardCnt = new int[10]; //원본
        int[] curCnt = new int[10]; //수를 생성하는 과정에 사용할 빈 배열(각 값은 원본보다 클수 없음)

        //각 숫자의 최대 개수를 관리할 배열을 생성
        for(int i=0;i<card.length;i++){
            cardCnt[card[i]]++;
        }

        //수를 생성하기 위한 함수 호출
        makeNum(cardCnt,curCnt,card.length,0);

        //System.out.println(numList.toString());
        //numList에서 n이 몇번째인지 찾아서 반환함
        if(numList.indexOf(n)>=0){
            answer=numList.indexOf(n)+1;
        }else answer=numList.indexOf(n);

        return answer;
    }
    
    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
        Solution sol = new Solution();
        int card1[] = {1, 2, 1, 3};
        int n1 = 1312;
        int ret1 = sol.solution(card1, n1);

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");

        int card2[] = {1, 1, 1, 2};
        int n2 = 1122;
        int ret2 = sol.solution(card2, n2);
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
    }    
}

정답

컨닝을 해서 풀었기 때문에 정답과 거의 유사합니다. 차이가 있는 부분은 재귀함수의 기저사례에 대해 저는 값을 감소시키는 방향이고, 이 예제는 값을 증가시키는 방향이라는 차이가 있습니다. 이 차이가 있어서 재귀함수의 인자값이 제가 하나더 적네요.

import java.util.*;

class Solution {
	ArrayList<Integer> num_list = new ArrayList<Integer>();

	//card 배열에 있는 숫자를 읽어서 각 숫자의 개수를 card_count에 집계하여 리터하는 함수
	public int[] cardCount(int[] card) {
		int card_count[] = new int [10];
	    for (int i = 0; i < card.length; i++) { //card_count의 0~9까지 인덱스에 각 숫자의 개수를 입력
	        card_count[card[i]]++;
	    }
	    return card_count;
	}

	//max_count에 집계되어있는 숫자 카드별 총 개수를 바탕으로
	//숫자 카드 모두를 사용한 수를 생성한 후 전역변수 num_list에 생성한 수를 추가하는 함수
	public void func_b(int level, int max_level, int num, int[] current_count, int[] max_count) {
	    if (level == max_level) {//사용한 숫자 카드 개수와 최대 카드 개수가 같으면
	    	num_list.add(num); //현재 생성한 수를 num_list에 추가
	        return;
	    }
	    for (int i = 1; i <= 9; i++) {
			//current_count 각 숫자별 사용한 개수가 각 숫자 카드별 총 개수 보다 작으면
	        if (current_count[i] < max_count[i]) {
	            current_count[i] += 1;
	            func_b(level + 1, max_level, num * 10 + i, current_count, max_count);//재귀호출
	            current_count[i] -= 1;
	        }
	    }
	}

	public int func_c(ArrayList<Integer> list, int n) {
	    for (int i = 0; i < list.size(); i++) {
	        if (n == list.get(i))
	            return i + 1;
	    }
	    return -1;
	}

	public int solution(int[] card, int n) {
	    int[] card_count = func_a(card);
	    func_b(0, card.length, 0, new int[10], card_count);
	    int answer = func_c(num_list, n);
	    return answer;
	}
}

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)