[백준] 2446번 : 별 찍기 - 9 - JAVA [자바]

 

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

2446번: 별 찍기 - 9

---

• 문제

 

 

별 찍기 응용문제로 가장 많이 나오는 문제 중 하나다.

 

처음에는 어떻게 해야할지 모르더라도 막상 이해한다면 매우 쉬운 문제이니 차근차근 살펴보자.

 

 

 

---

• 3가지 풀이방법을 제시한다

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

또한 BufferedReader 에서 출력방법을 바꿔보며 어느 방법이 시간을 더 단축 시킬 수 있는지 한 번 보고자 한다.

 

 

---

• 알고리즘

출력 행은 총 2N-1 줄 이다.

 

먼저 N 이라는 숫자가 주어진다.

 

1. 1 행부터 N 행까지 출력을 하기 위한 가장 큰 틀의 반복문을 먼저 구상한다.

for (int i = 0; i < N; i++)

 

 

2. 그리고 출력을 보면  공백이 1 행에 0개 출력, 2행에 1개 출력, ...

즉, n 번째 행에는 n - 1 개의 공백이 출력된다.

 

다만 i 를 0 으로 초기화 했다. 

이 이유는 이후에 설명하겠다.

 

고로, 1 ~ N 행까지의 공백 출력에 대해 위의 for문 안에 for문 ( 이중for문 ) 을 작성해본다면 아래와 같을 것이다.

for (int i = 0; i < N; i++){
	for(int j = 0 ; j < i; j++) {
		print(" ");
	}
}

공백 출력의 경우 내부 for문의 j 는 해당 행의 -1 개 만큼, 즉 i 의 수 만큼 공백을 출력하면 된다.

 

 

3. 공백이 출력되었으면 별을 출력해야 한다.

별의 개수를 잘 보자.

 

N = 5 일 때 첫 행의 별의 개수는 몇개인가? 9 개다.

다음 행은? 7개다. 이렇게 -2 씩 줄여가면서 출력되는 것을 볼 수 있다.

 

그럼 N = 4 일 때는 첫 행의 별의 개수는 몇 개 일까?

위에서 N = 5 일 때 두 번째 줄이 7개 였듯이 N = 4 이면 당연히 7 개 일 것이다.

 

즉 표로 보자면

N = N	2N - 1
N = 5	9
N = 4	7
N = 3	5
N = 2	3
N = 1	1

 

우리는 피라미드가 거꾸로 있는 모양, 즉 역순으로 수가 줄어들기 때문에 첫 항은 항상 입력받은 값 N 에 2를 곱하고 -1 을 한 값이다.

수식으로 말하자면 2N - 1 이라는 말이다.

 

그럼 반복문으로 돌아가서 한 번 생각해보자.

 

N = 5 일 경우를 보자.

첫 행은 9 개( 5x2 - 1 )가 출력되어야 한다. 그리고 첫 행은 i = 0 이다.

 

두 번째 행은 7 개가 출력되어야 한다. 이 때 i = 1 이다. 그러면 ( 5x2 - 1 ) 에 ( i x 2 ) 를 빼주면 되지 않는가? 다음 행은 어떨까?

 

세 번째 행은 5개가 출력되어야 한다. 이 때 i = 2 이다. 위 식에 대입해보면 ( 5x2 - 1 ) - ( 2 x 2 ) = 5 가 된다.

즉 이를 수식으로 정리하면 다음과 같다.

 

별 출력 개수 = ( N x 2 - 1 ) - ( i x 2 ) 

 

그럼 위 식을 토대로 for 문을 작성해보자.

for (int i = 0; i < N; i++){	// 1 ~ N
	for(int j = 0; j < i; j++) {	// 공백
		print(" ");
	}
    
	for(int k = 0; k < (2 * N - 1) - (2 * i); k++){	// 별
		print("*");
	}
	print('\n');
}

 

감이 오는가? k 는 0 부터 해서 ((2N-1) - 2i) 보다 작을 때 까지 출력해주면 되는것이다.

 

또한, 한 행의 출력이 모두 끝나면 개행(줄바꿈)을 해주어야되지 않겠는가?

그러므로 내부 for 문 두 개가 종료 될 때마다 개행을 해주면 되겠다.

 

 

여기까지만 짜면 딱 역삼각형까지 출력 된 것이다.

 

---

 

역삼각형 다음으로는 삼각형을 구현해야하니 이 또한 함께 봐보자.

 

4. 삼각형의 경우 일단 역삼각형에서 N 행까지 출력했기 때문에 N+1 행부터 시작한다.

즉, 전체 출력 행의 개수가 2N-1 이었으므로 역삼각형에서 N+1 까지 행을 출력했기 때문에 이를 빼주면 삼각형의 경우 총 출력 개수는 N-1 개를 출력하게 된다. 

// 역삼각형 코드 생략

for (int i = 0; i < N - 1; i++){	// N+1 ~ 2N-1
}

 

이런식으로 구조를 짜면 된다.

 

5. 그러면 공백을 이제 출력해야한다.

여기서 잘 생각해야하는 것이 우리는 N+1 부터 출력했다는 것이다.

 

즉, 원래 삼각형의 한 행을 건너 띄어야 한다는 점이다.

또한 삼각형의 반복문에서 공백의 개수는 1 개씩 감소한다.

 

잘 이해 안된다면 아래 표를 보자.

N+1 번째 줄을 J 라고 생각하자. 그리고 i 는 우리가 for 문에서 썼던 변수 i 의 값을 말한다.

 

* N = 4 일 때

J 번째 행	공백 개수	별 개수	i
J = 1  (N+1)	2	3	0
J = 2  (N+2)	1	5	1
J = 3  (N+3)	0	7	2

 

 

* N = 5 일 때

J 번째 행	공백 개수	별 개수	i
J = 1  (N+1)	3	3	0
J = 2  (N+2)	2	5	1
J = 3  (N+3)	1	7	2
J = 4  (N+4)	0	9	3

 

 

* N = 6 일 때

J 번째 행	공백 개수	별 개수	i
J = 1  (N+1)	4	3	0
J = 2  (N+2)	3	5	1
J = 3  (N+3)	2	7	2
J = 4  (N+4)	1	9	3
J = 5  (N+5)	0	11	4

 

 

 

위 3가지를 보면 감이 오는가?

위 표를 보면 우리는 두 가지 특징을 발견 할 수 있다.

 

1. 첫 행의 별 개수는 항상 3 개다. (N=1 경우 제외)
2. 첫 행의 공백 개수는 항상 N-2 개다. (N=1 경우 제외)
3. i 와 공백의 개수는 역이다. 즉 입력값 N에 대하여 N - 2 - i 이 공백의 개수다. (단 아래 코드에서 보면 j = 1 부터 시작하므로  N - 1 - i 까지가 된다)

 

 

즉, 공백 부분은 아래와 같이 짤 수 있다. 

// 역삼각형 코드 생략

for (int i = 0; i < N - 1; i++){	// N+1 ~ 2N-1
	for(int j = 1; j < (N - 1) - i; j++) {	// 공백
		print(" ");
	}
}

 

 

 

6. 별의 개수는 아까 위의 그림을 보면 공식 또한 알 수 있다.

일단 첫 행은 무조건 3개다. 그리고 매 항마다 2개씩 증가한다는 것을 볼 수 있다. 이때 i 는 0 부터 시작한다.

 

즉, 3 + 2i 개수 만큼 출력해주면 된다는 것이다.

 

// 역삼각형 코드 생략

for (int i = 0; i < N - 1; i++){	// N+1 ~ 2N-1
	for(int j = 1; j < (N - 1) - i; j++) {	// 공백
		print(" ");
	}
    
	for(int k = 0; k < 3 + (2 * i); k++) {	// 별
		print("*");
	}
	print('\n');
}

 

이러면 삼각형 출력부분이 완성된다.

 

그러면 역삼각형 코드와 삼각형 코드를 합치면 다음과 같다.

 

 

// 역삼각형 코드
for (int i = 0; i < N; i++){	// 1 ~ N
	for(int j = 0; j < i; j++) {	// 공백
		print(" ");
	}
    
	for(int k = 0; k < (2 * N - 1) - (2 * i); k++){	// 별
		print("*");
	}
	print('\n');
}

// 삼각형 코드
for (int i = 0; i < N - 1; i++){	// N+1 ~ 2N-1
	for(int j = 1; j < (N - 1) - i; j++) {	// 공백
		print(" ");
	}
    
	for(int k = 0; k < 3 + (2 * i); k++) {	// 별
		print("*");
	}
	print('\n');
}

 

 

 

 

생각보다 쉽지 않은가? (아니면 어쩔 수 없다만..)

 

그럼 전체 코드를 보여주겠다.

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		// 역삼각형 코드
		for (int i = 0; i < N; i++) {	// 1 ~ N

			// 공백
			for (int j = 0; j < i; j++) {
				System.out.print(" ");
			}

			// 별
			for (int k = 0; k < (2 * N - 1) - (2 * i); k++) {
				System.out.print("*");
			}

			System.out.println();
		}

		// 삼각형 코드
		for (int i = 0; i < N - 1; i++) {	// N+1 ~ 2N-1
        
			// 공백
			for (int j = 1; j < (N - 1) - i; j++) {	
				System.out.print(" ");
			}

			// 별
			for (int k = 0; k < 3 + 2 * i; k++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

}

 

 

가장 기본적인 방법이다.

그리고 무의식 중에 내부 for문 안에 System.out.println("*") 을 하다간 큰일난다...

 

 

---

 

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

 

그리고 반드시 자료형 타입을 잘 보아야 한다.

br.readLine() 은 문자열로 데이터를 읽으니 반드시 꺼내서 쓸 때 int 형으로 쓰고자 한다면 Integer.parseInt()로 String 을 int 형으로 변환시켜준다.

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

public class Main {

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

		int N = Integer.parseInt(br.readLine());

		// 역삼각형 코드
		for (int i = 0; i < N; i++) {	// 1 ~ N

			// 공백
			for (int j = 0; j < i; j++) {
				System.out.print(" ");
			}

			// 별
			for (int k = 0; k < (2 * N - 1) - (2 * i); k++) {
				System.out.print("*");
			}

			System.out.println();
		}

		// 삼각형 코드
		for (int i = 0; i < N - 1; i++) {	// N+1 ~ 2N-1
        
			// 공백
			for (int j = 1; j < (N - 1) - i; j++) {	
				System.out.print(" ");
			}

			// 별
			for (int k = 0; k < 3 + 2 * i; k++) {
				System.out.print("*");
			}
			System.out.println();
		}
	}

}

 

 

위 코드를 실행하면 물론 Scanner 보다 BufferedReader 가 속도가 빠르니 시간이 단축되지만 출력 부분에서 System.out.print() 를 너무 자주 호출해주기 때문에 이 부분에서 좀 더 시간을 절약해볼 방법을 알아보자. 

 

---

- 방법 3

 

다음 방법은 StringBuilder 을 사용하여 출력하는 방법이다.

모든 문자열을 하나의 객체에 연결해준다음 출력은 마지막에 한 번만 해주니 시간을 아낄 수 있는 방법 중 하나다.

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

public class Main {

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

		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();


		// 역삼각형 코드
		for (int i = 0; i < N; i++) {	// 1 ~ N

			// 공백
			for (int j = 0; j < i; j++) {
				sb.append(' ');
			}

			// 별
			for (int k = 0; k < (2 * N - 1) - (2 * i); k++) {
				sb.append('*');
			}

			sb.append('\n');
		}


		// 삼각형 코드
		for (int i = 0; i < N - 1; i++) {	// N+1 ~ 2N-1
        
			// 공백
			for (int j = 1; j < (N - 1) - i; j++) {
				sb.append(' ');
			}

			// 별
			for (int k = 0; k < 3 + 2 * i; k++) {
				sb.append('*');
			}
			sb.append('\n');
		}
        
        
		System.out.println(sb);
	}

}

 

 

---

• 성능 차이

 

위에서 부터 순서대로

 

채점 번호 : 18405020  -  BufferedReader + StringBuilder 

채점 번호 : 18405005 -  BufferedReader + System.out.print

채점 번호 : 18404999 -  Scanner + System.out.print

시간을 보면 BufferedReader 와 Scanner 의 성능차이 및 출력 방법에 따른 성능 차이 또한 볼 수 있다.

이번 문제는 특히 출력에서 많이 차이가 난다.

 

 

---

• 정리

막상 이미지로만 생각하면 어려울 수 있지만 이렇게 수식을 정리해서 풀어보면 아주 단순한 문제다.

 

그리고 필자의 코드가 어쩌다 보니 자바 제출자 중 1 등을 했다.. 많은 참고가 되길 바란다.

*인증사진