[BOJ] 15654:N과 M (5)

0. 문제

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

15654번: N과 M (5)

1. 문제분석

-  주어진 수들을 순차적으로 다르게 배열한 모든 경우의 수만 제시하면 되는 비교적 간단한 형태의 BackTracking 문제이다.

 

2. 주의할 점

- 꽤나 간단한 문제이기는 하지만, 꽤 많은 양을 출력해야 하므로 출력과 관련한 시간초과 문제를 조심해야 한다.

- 기존에 사용하던 자료구조(스택, 큐, 그래프 등)를 구현한 라이브러리(LinkedList, ArrayList 등) 클래스에 있는 메소드를 사용해 문제를 풀 수도 있지만, 비교적 단순한 자료구조인 단순 배열만으로도 문제를 충분히 풀 수 있다.

 

3. 소스코드(Java)

3-1. 시간초과 소스코드

// boj 15654 : N과 M (5)
// backtracking

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class boj_15654 {
    static int N, M;
    static int[] numbers;
    static boolean[] used;
    static LinkedList<Integer> stack = new LinkedList<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        st = new StringTokenizer(br.readLine());
        numbers = new int [N];
        used = new boolean [N];
        for (int i = 0; i < N; ++i) numbers[i] = stoi(st.nextToken());
        Arrays.sort(numbers);
        go();
    }
    static int stoi(String s) {return Integer.parseInt(s);};
    static void go() {
        if (stack.size() >= M) {
            for (int a : stack) System.out.print(a+" ");
            System.out.print("\n");
            return;
        }
        for (int i = 0; i < N; ++i) {
            if (used[i]) continue;
            used[i] = true; stack.add(numbers[i]);
            go();
            used[i] = false; stack.pollLast();
        }
    }
}

 

3-2. 통과한 소스코드

// boj 15654 : N과 M (5)
// backtracking

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_15654 {
    static int N, M;
    static int[] numbers, stack;
    static boolean[] used;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        st = new StringTokenizer(br.readLine());
        numbers = new int [N];
        stack = new int [M];
        used = new boolean [N];
        for (int i = 0; i < N; ++i) numbers[i] = stoi(st.nextToken());
        Arrays.sort(numbers);
        go(0);
        System.out.print(sb);
    }
    static int stoi(String s) {return Integer.parseInt(s);}
    static void go(int num) {
        if (num >= M) {
            for (int i = 0; i < M; ++i) sb.append(stack[i]).append(' ');
            sb.append('\n');
            return;
        }
        for (int i = 0; i < N; ++i) {
            if (used[i]) continue;
            used[i] = true; stack[num] = numbers[i];
            go(num + 1);
            used[i] = false;
        }
    }
}

4. 여담

- 잘 풀었다고 생각했는데 시간초과가 떠서 매우 당황했다.... 저번에 알아두었던 StringBuilder였는데도 바로 생각이 나지는 않았따.. I/O 시간지체... 앞으로는 먼저 해결해놓고 알고리즘을 생각해야지..!