코딩 테스트 [조합] - 사전 찾기

동호와 규완이는 212호에서 문자열에 관해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 줬다. 특별 과제는 특별한 문자열로 이뤄진 사전을 만드는 것이다. 사전에 수록돼 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이뤄져 있다. 다른 문자는 없다. 사전에는 알파벳 순서대로 수록돼 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이기 자리를 비운 사이에 몰래 사전을 보려고 하므로 문자열 1개만 찾을 여유밖에 없다. N과 M이 주어졌을 때 규완이의 사전애서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

(시간 제한 2초)

---

입력

1번째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수, K는 1,000,000,000보다 작거나 같은 자연수다.

출력

1번째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록돼 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

예제 입력
2 2 2	// N(a의 개수), M(z의 개수), K
 
예제 출력
azaz

---

1단계 - 문제 분석하기

사전에서 다루는 문자열이 a와 z밖에 없다는 점에 착안해 접근해 보겠다. 핵심 아이디어는 a와 z의 개수가 각각 N, M개일 때 이 문자들로 만들 수 있는 모든 경우의 수는 N + M개에서 N개를 뽑는 경우의 수 또는 N + M개에서 M개를 뽑는 경우의 수와 동일하다.

2단계 - 손으로 풀어 보기

1 조합의 경우의 수를 나타내는 D배열을 초기화하고, 점화식으로 값을 계산해 저장한다.

• D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
  

2 몇 번째 문자열을 표현해야 하는지를 나타내는 변수를 K라고 한다. 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수는 T다. T와 K를 비교해 문자를 선택한다.

• T ≥ K : 현재 자리 문자를 a로 선택
• T < K : 현재 자리 문자를 z로 선택하고, K = K - T로 업데이트

3 과정 2를 a와 z의 문자들의 수를 합친 만큼 반복해 정답 문자열을 출력한다.

확정된 문자를 차례대로 출력 => azaz

3단계 - sudo코드 작성하기

N(a 문자 개수) M(z 문자 개수) K(순번)

for(i -> 0 ~ 200)
{
	for(j -> 0 ~ i)
    {
    	D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
        D[i][j] 값이 K의 범위를 벗어낫을 때 K 범위의 최댓값으로 D[i][j] 조장하기
    }
}

if(불가능한 K이면)
	-1 출력

while(모든 문자를 사용할 때까지)
{
	if(a 문자를 선택했을 때 남은 문자들로 만들 수 있는 모든 경우의 수 >= K)
    {
    	a 출력, a문자 개수 감소(N--)
    }
    else
    {
    	z 출력, z문자 개수 감소(M--), k의 값을 계산된 모든 경우의 수를 뺀 값으로 저장
    ]
}

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q82 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();

        int[][] D = new int[202][202];
        for(int i = 0; i <= 200; i++){
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    D[i][j] = 1;
                }else{
                    D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
                    if(D[i][j] > 1000000000){
                        D[i][j] = 1000000001;
                    }
                }
            }
        }

        if(D[N + M][M] < K){
            System.out.println("-1");
        }else {
            while(!(N == 0 && M == 0)){
                if(D[N + M - 1][M] >= K){
                    System.out.print("a");
                    N--;
                }else{
                    System.out.print("z");
                    K = K - D[N + M - 1][M];
                    M--;
                }
            }
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편