이 문제는 중복순열 문제이다.
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를 쓰는 게 훨씬 빠르다.
(그 이유는
이 글을 보면 나와있다)
3. 줄바꿈을 하고 싶으면 System.out.println()을 쓰는게 아니라 StringBuilder에 "\n"을 계속 append 하고 줄마다 출력하는게 아니라 한번에 출력하는 것이 훨씬 빠르다.
앞으로는 이런 헛수고 하지 않게 명심하자!
'알고리즘 문제' 카테고리의 다른 글
[백준] 9963번 N-Queen (0) | 2020.01.06 |
---|---|
[백준] 15652번 N과 M (4) (0) | 2020.01.06 |
[백준] 15650번 N과 M (2) (0) | 2020.01.06 |
[백준] 15649번 N과 M (1) (0) | 2020.01.06 |
[백준] 14502번 연구소 (0) | 2020.01.05 |