순열(n과m 문제) 최적화 시키기 && 조합

실행시간 단축 방법

보통의 지문 : 자연수 N과 M이 주어졌을 때 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 순열을 구하라.

 

1. StringBuilder 로 결과 출력하기

 

2. 백트래킹 하면서 순열 결과값을 저장하는 변수를 Array로 사용하기

     2-1. 왜 그럴까? Array를 사용하면 Array의 cnt 인덱스에 값을 계속 갱신하기 때문에 ArrayList 를 사용할 때 필요한 list.remove(list.size()-1); 의 과정이 필요없다. 

 

3. (특정 문제상황) input에 대해 중복을 제거하는 과정을 거쳤다면, 만들어진 comb에 대해 중복을 검사하는 과정은 필요없다.

      3-1. 이미 input에서 중복 원소를 제거했기 때문에 만들어지는 순열에는 중복된 순열이 존재할 수 없다.

 

package com.mincheolsong;

import java.util.*;
import java.io.*;

public class Main {

    static int N,M;
    static List<Integer> list;
    static Set<Integer> set;
    static StringBuilder sb = new StringBuilder(); // StringBuilder 사용
    static int[] comb; // Array 사용

    static void solve(int cnt){
        if(cnt == M){
			// 중복로직 필요 없음 (이미 main함수에서 input의 중복을 제거했기 때문에)
            for(int i=0;i<M;i++){
                sb.append(comb[i]).append(" ");
            }
            sb.append("\n");

            return;
        }


        for(int i=0;i<N;i++){
            comb[cnt] = list.get(i); 
            solve(cnt+1);
            // Array의 cnt위치에 값을 계속 갱신하기 때문에 backTracking 함수의 특징인 원복 코드가 필요 없음
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        comb = new int[M];
        set = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            set.add(Integer.parseInt(st.nextToken()));
        }

        for(Integer i : set){
            list.add(i);
        }

        Collections.sort(list);
        N = list.size();

        solve(0);

        System.out.print(sb.toString());
    }
}

 

조합 코드는 비내림차순 순열 코드와 같다

조합을 구현하는 코드는 비내림차순 순열 코드와 같다

(아래 코드는 1,2,3,4 에서 3개를 뽑는 경우의 조합)

import java.util.*;

public class Main {


    static int[] comb;
    static int[] n = {1,2,3,4};

    static void solve(int start,int cnt){

        if(cnt==3){
            System.out.println(Arrays.toString(comb));
            return;
        }

        for(int i=start;i<4;i++){
            comb[cnt] = n[i];
            solve(i+1,cnt+1);
        }
    }

    public static void main(String[] args) {

        comb = new int[3];
        solve(0,0);

    }
}