[백준] 15651 N과 M (3)

이 문제는 중복순열 문제이다.

15651번: N과 M (3)

N과 M (1), N과 M (2)를 쉽게 풀었기 때문에 N과 M (3)을 보자마자 이건 더 쉬운데? 했다.

중복순열이기 때문에 boolean 타입의 visited[n] 배열을 따로 유지할 필요가 없어서 코드도 더 짧고 더 쉬웠다.

15649번 코드에서 visited 관련된 코드만 삭제한 코드인

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] result = new int[m];
        permutationWithRepetition(n, m, 0, result);
    }

    static void permutationWithRepetition(int n, int m, int num, int[] result) {
        if (num == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            result[num] = i + 1;
            permutationWithRepetition(n, m, num + 1, result);
        }
    }
}

이렇게 제출했다.

그랬더니

시간초과가 났다.

 

그래서 이렇게 해봤는데

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] result = new int[m];
        for(int i = 0; i < Math.pow(n, m); i++) {
            for (int j = 0; j < m; j++) {
                System.out.print((int)(i / Math.pow(n, m - j - 1)) % n + 1 + " ");
            }
            System.out.println();
        }
    }
}

이래도 시간초과가 났다.

그래서 동적계획법으로 해야하나 하고 정말 두 시간 동안 별 짓을 다 해봤다.

그런데도 계속 시간 초과가 나는거다.

내가 정답률 70% 짜리 문제에 이렇게 시간을 투자하고 있다는게 너무 어이없어서 결국 구글링을 해봤다.

그랬더니 시간 초과의 원인은 바로 입출력에 있었다.

내가 처음 짠 코드 그대로에 입출력만 다르게 했더니 성공했다.

StringBuilder와 String의 차이에 대한 글을 포스팅까지 했는데 써먹지를 않았고 지난학기 자바 응용 수업에서 입출력스트림을 그렇게 많이, 자세히 배웠는데도 써먹지를 않은 나를 반성하게 되었다.

 

처음 짰던 그 코드에서 입출력하는 부분만 바꿔서

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

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        StringBuilder sb = new StringBuilder();
        try {
            s = br.readLine();
        } catch (IOException e) {}
        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] result = new int[m];
        permutationWithRepetition(n, m, 0, result, sb);
        System.out.println(sb);
    }
    static void permutationWithRepetition(int n, int m, int num, int[] result, StringBuilder sb) {
        if (num == m) {
            for (int i = 0; i < m; i++) {
                sb.append(result[i] + " ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < n; i++) {
            result[num] = i + 1;
            permutationWithRepetition(n, m, num + 1, result, sb);
        }
    }
}

이렇게 제출했더니 성공했다.

 

괜히 쓸데없이 2시간을 버린 것 같아서 약간 허탈하지만 덕분에 매우 중요한 것을 알게 되었다.

1. Scanner, System.out.print()보다 InputStreamReader를 쓰는게 더 빠르다.

2. 문자열에 계속 + " " 이런식으로 append할 일이 많으면 StringBuilder를 쓰는 게 훨씬 빠르다.

(그 이유는

[Java] String, StringBuilder, StringBuffer의 차이점

이 글을 보면 나와있다)

3. 줄바꿈을 하고 싶으면 System.out.println()을 쓰는게 아니라 StringBuilder에 "\n"을 계속 append 하고 줄마다 출력하는게 아니라 한번에 출력하는 것이 훨씬 빠르다. 

 

앞으로는 이런 헛수고 하지 않게 명심하자!