[백준 - 1256번] 사전 - Java //Wello Horld//

이번에는 백준알고리즘의 1256번 문제 "사전"을 풀어보도록 하자

문제를 이해하기 약간 애매한 부분이 있어서, 예제를 보면서 설명하도록 하겠다. 일단, 입력으로는 "a"의 개수인 N, "z"의 개수인 M, 마지막으로 K가 주어지고, 출력으로 사전에서 K번째 문자열이 무엇인지 구하면 되는 프로그램이다. 여기에서, K의 상한이 1,000,000,000(십억)이므로 정수형(long)으로 받아야된다. 먼저 예제를 보면,

• 입력 : 2 2 2
• 출력 : azaz

이 주어졌다. 2개의 "a"와 2개의 "z"로 되어진 문자열 중 사전에서 2번째 문자열은 "aazz"다음인 "azaz"가 되므로, 출력으로 "azaz"를 내보내면 된다.

이번문제는, combination을 이용해서 문제를 풀었다. BigInteger를 이용해서 아래와 같이 combination을 구하는 메서드를 구현했다.

public static BigInteger combination(int N, int M){
    BigInteger combiup = new BigInteger("1");
    BigInteger combidown = new BigInteger("1");
    for(int i = 1; i <= N; i++){
        combiup = combiup.multiply(new BigInteger(String.valueOf((N+M)-(i-1))));
        combidown = combidown.multiply(new BigInteger(String.valueOf(i)));
    }
    return combiup.divide(combidown);
}

성공한 전체코드는 아래와 같다.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        BigInteger K = new BigInteger(st.nextToken());
        BigInteger combi = combination(N, M);
        if(combi.compareTo(K) == -1){
            bw.write("-1" + "\n");
        } else {
            String ans = "";
            combi = BigInteger.ZERO;
            while(combi.compareTo(K) != 0){
                BigInteger combiTemp = combi;
                combi = combi.add(combination(N - 1, M));
                if(combi.compareTo(K) == -1){
                    M--;
                    ans += "z";
                } else {
                    N--;
                    ans += "a";
                    combi = combiTemp;
                }
                if(N == 0 || M == 0){
                    break;
                }
            }
            for(int i = 1; i <= M; i++){
                ans += "z";
            }
            for(int i = 1; i <= N; i++){
                ans += "a";
            }
            bw.write(ans + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }

    public static BigInteger combination(int N, int M){
        BigInteger combiup = new BigInteger("1");
        BigInteger combidown = new BigInteger("1");
        for(int i = 1; i <= N; i++){
            combiup = combiup.multiply(new BigInteger(String.valueOf((N+M)-(i-1))));
            combidown = combidown.multiply(new BigInteger(String.valueOf(i)));
        }
        return combiup.divide(combidown);
    }
}

1256번: 사전

문졔 : https://www.acmicpc.net/problem/1256