문제
레벨: G5
알고리즘:
풀이시간: 1시간
힌트 참조 유무: 무
https://www.acmicpc.net/problem/2447
1 번째 시도
[풀이 사고 과정]
- 처음 주어진 패턴으로 부분요소들을 크게 업데이트 해가는 문제구나 라는 생각
- 즉, 재귀함수 문제라 생각
- 풀이는 코드 주석 참조
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[][] patern = {
{"*", "*", "*"},
{"*", " ", "*"},
{"*", "*", "*"}
};
print(N, 3, patern);
}
public static void print(int N, int now, String[][] arr) {
int pre = now / 3;
String[][] nowArr = new String[now][now];
for (int i = 0; i < now; i++) {
for (int j = 0; j < now; j++) {
// 현재 배열 중 가운데에 통빈칸을 넣어야 하므로
if (i + 1 > now / 3 && i + 1 <= now / 3 * 2 && j + 1 > now / 3 && j + 1 <= now / 3 * 2) {
nowArr[i][j] = " ";
} else {
nowArr[i][j] = arr[i % pre][j % pre]; //그외에는 이전배열의 모음이므로
}
}
}
if (now == N) {
StringBuilder sb = new StringBuilder(); //배열 인덱스를 각각 sout하면 시간 초과 걸릴 것 같아 sb이용
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(nowArr[i][j]);
}
sb.append("\n");
}
System.out.println(sb);
return;
}
print(N, now * 3, nowArr);
}
}
번외
- StringBuilder 대신 sout를 찍어보면 얼마나 걸릴까 궁금해 직접 테스트 해보았다
- 두 개의 테스트는 입력값의 최대인 6561(3의 8승)으로 테스트 해보았다.
- 3의 8승으로 진행해보았으나 System.out.prinln 버전이 2분이 지나도 출력이 멈추지 않아 243(3의 5승)으로 테스트했습니다
System.out.println 버전: 481ms
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[][] pattern = {
{"*", "*", "*"},
{"*", " ", "*"},
{"*", "*", "*"}
};
// Start time
long startTime = System.currentTimeMillis();
print(N, 3, pattern);
// End time
long endTime = System.currentTimeMillis();
// Calculate and print the elapsed time
long elapsedTime = endTime - startTime;
System.out.println("Elapsed time: " + elapsedTime + " ms");
}
public static void print(int N, int now, String[][] arr) {
int pre = now / 3;
String[][] nowArr = new String[now][now];
for (int i = 0; i < now; i++) {
for (int j = 0; j < now; j++) {
// 현재 배열 중 가운데에 통빈칸을 넣어야 하므로
if (i + 1 > now / 3 && i + 1 <= now / 3 * 2 && j + 1 > now / 3 && j + 1 <= now / 3 * 2) {
nowArr[i][j] = " ";
} else {
nowArr[i][j] = arr[i % pre][j % pre]; //그외에는 이전배열의 모음이므로
}
}
}
if (now == N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(nowArr[i][j]);
}
System.out.println(); // Added to properly format the output
}
return;
}
print(N, now * 3, nowArr);
}
}
StringBuilder 버전: 17ms
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[][] pattern = {
{"*", "*", "*"},
{"*", " ", "*"},
{"*", "*", "*"}
};
// Start time
long startTime = System.currentTimeMillis();
// Call the print function
print(N, 3, pattern);
// End time
long endTime = System.currentTimeMillis();
// Calculate and print the elapsed time
long elapsedTime = endTime - startTime;
System.out.println("Elapsed time: " + elapsedTime + " ms");
}
public static void print(int N, int now, String[][] arr) {
int pre = now / 3;
String[][] nowArr = new String[now][now];
for (int i = 0; i < now; i++) {
for (int j = 0; j < now; j++) {
// 현재 배열 중 가운데에 통빈칸을 넣어야 하므로
if (i + 1 > now / 3 && i + 1 <= now / 3 * 2 && j + 1 > now / 3 && j + 1 <= now / 3 * 2) {
nowArr[i][j] = " ";
} else {
nowArr[i][j] = arr[i % pre][j % pre]; //그외에는 이전배열의 모음이므로
}
}
}
if (now == N) {
StringBuilder sb = new StringBuilder(); //배열 인덱스를 각각 sout하면 시간 초과 걸릴 것 같아 sb이용
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(nowArr[i][j]);
}
sb.append("\n");
}
System.out.println(sb);
return;
}
print(N, now * 3, nowArr);
}
}