[Java] 15651번 : N과 M (3)

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

아 망할놈의 시간초과 진짜,,,

 

오늘도 어김없이 나오는 시간초과 ㅎㅎ

 

문제는 간단한 문제였다. 그냥 순열 구하는 문제였는데, 중복을 다 허용해서 구하면 된다! 

https://gyuwon95.tistory.com/136

[Java] 순열(Permutation), 조합(Combination)

사실 좀 까먹어서 이거 보고 재귀 다시 한번 돌려보고 다시 풀었다 ㅎㅎ,,,,

기억력 쓸애기 ㅎㅎ 

 

순열 permutation 함수

 

ArrayList a 는 입력받는 리스트, 그리고 output은 출력하려는 배열, depth 는 현재 탐색하고 있는 인덱스, r 은 몇개를 뽑을건지 이다! 

재귀를 이용해서 리스트를 순회하면서 depth를 하나씩 올려주었다.

public static void permutation(ArrayList<Integer> a, int output[], int depth, int r) {

        if(depth==r) {
            for(int i=0;i<r;i++) {
                sb.append(output[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i=0;i< a.size();i++) {
            output[depth] = a.get(i);
            permutation(a, output, depth + 1, r);
        }

    }

 

main

 

시간초과의 원인은 처음에 StringBuilder 를 사용하지 않고, System.out.println을 사용했기 때문이다,,,

앞으로 StringBuilder를 생활화하자,,,,!

 static int n, m;
    static StringBuilder sb = new StringBuilder();

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

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        ArrayList<Integer> a = new ArrayList<>();
        for(int i=0;i<n;i++) {
            a.add(i+1);
        }
        int output[] = new int[a.size()];
        permutation(a, output, 0, m);
        System.out.println(sb);

    }

 

[전체코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        static int n, m;
        static StringBuilder sb = new StringBuilder();

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

            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            ArrayList<Integer> a = new ArrayList<>();
            for(int i=0;i<n;i++) {
                a.add(i+1);
            }
            int output[] = new int[a.size()];
            permutation(a, output, 0, m);
            System.out.println(sb);

        }
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        ArrayList<Integer> a = new ArrayList<>();
        for(int i=0;i<n;i++) {
            a.add(i+1);
        }
        int output[] = new int[a.size()];
        permutation(a, output, 0, m);
        System.out.println(sb);

    }


    public static void permutation(ArrayList<Integer> a, int output[], int depth, int r) {

        if(depth==r) {
            for(int i=0;i<r;i++) {
                sb.append(output[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i=0;i< a.size();i++) {
            output[depth] = a.get(i);
            permutation(a, output, depth + 1, r);
        }

    }

}