백준 - 15651 - N과 M(3)

www.acmicpc.net/problem/15651

15651번: N과 M (3)

import java.util.Scanner;

/**
 * 백준 15651
 * 순열 - 중복 허용
 */
public class N과_M_3 {
    private static int N;
    private static int[] num;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);
        num = new int[M+1];
        //printPermutation(M, new StringBuilder());
        printPermutation2(M, "");
        System.out.println(sb);
    }

    /**
     *
     * @param N : 범위
     * @param M : 자릿수
     */
    // 시간 초과 버전
    private static void printPermutation(int M, StringBuilder prefix) {
        if(M == 0) {
            System.out.println(prefix.toString().trim());
            return;
        }

        for(int i=1; i<=N; i++) {
            prefix.append(i + " ");
            printPermutation(M-1, prefix);
            prefix.delete(prefix.length()-2, prefix.length());
        }
    }

	//공간복잡도는 올라가지만 시간 성능을 높인 버전
    private static StringBuilder sb = new StringBuilder();
    private static void printPermutation2(int M, String str) {
        if(M == 0) {
            sb.append(str.trim() + "\n");
            return;
        }

        for(int i=1; i<=N; i++) {
            printPermutation2(M-1, str + " " + i);
        }
    }
}

문제

중복 요소가 있는 순열

 

알고리즘

• 백트래킹, 순열
• StringBuilder를 사용하여 공간복잡도를 낮추려고 했으나 시간초과에 걸리게 됐습니다.
• 매번 스택에서 StringBuilder의 append와 delete를 하는데 생각보다 비용이 큰것 같습니다.
• 그래서 StringBuilder를 String으로 대체하여 사용하고 종료조건인 경우에만(M == 0) String을 append하는 구조로 변경하여 시간복잡도를 낮췄습니다.