[백준] 10996번 : 별 찍기 - 21 - JAVA [자바]

 


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

10996번: 별 찍기 - 21

---

• 문제

 

 

 

 

 

위 문제는 다른 별 찍기에 비해 쉬운 편이다!

아래 알고리즘에서 한 번 차근차근 알아보자.

---

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

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

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

 

 

---

• 알고리즘

먼저 출력 방법을 자세히 보자.

 

 

 

 

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

 

그럼 총 출력 행은 2N 개다.

 

이 N 이라는 숫자에 따라 1 행부터 2N 행까지 출력을 하기 위한 가장 큰 틀의 반복문을 먼저 구상한다.

for ( int i = 1 ; i <= 2*N ; i++ )

 

 

 

2. 출력을 보면 별과 공백이 번갈아 가며 출력이 된다.

 

홀수행 ( i = 1, 3, 5, ... ) 에는 별 부터, 짝수행 ( i = 2, 4, 6, ... ) 에는 공백부터 출력된다.

또한 한 행의 공백과 별의 총 출력 개수는 N 개다.

 

 

 

즉, for 문의 i 에 따라 두 가지 케이스로 나뉘게 된다. 코드를 짜면 다음과 같다.

for(int i = 1; i <= 2*N; i++){
 
	// 홀수 행
	if(i % 2 == 1){
	}
 
	// 짝수 행
	else{
	}
 
}

 

 

3. 그리고 각 행마다 조건문에 의해 별 또는 공백부터 N개를 출력하기 위한 반복문을 작성한다.

for(int i = 1; i <= 2*N; i++){
 
	// 홀수 행
	if(i % 2 == 1){
		for(int j = 1; j <= N; j++){
		}
	}
 
	// 짝수 행
	else{
		for(int j = 1; j <= N; j++){
		}
	}
 
}

 

 

 

4. 그리고는 각 행 마다 별 또는 공백을 번갈아가며 출력을 해주어야한다.

홀수 행에는 별 부터 출력하기 때문에 j 가 홀수 ( 1, 3, 5, 7, ... ) 일 때는 별을, 짝수 ( 2, 4, 6, ... ) 일 때는 공백을 출력하는 조건문을 써주고,

 

짝수 행에는 위와 반대로 작성해주면 된다. 즉 아래와 같이 되겠다.

( 그리고 반복문 한 회당 개행(줄바꿈)을 하는 것을 잊지 않도록 한다. )

for(int i = 1; i <= 2*N; i++){
 
	// 홀수 행
	if(i % 2 == 1){
		for(int j = 1; j <= N; j++){
			// 홀수 번째
			if(j % 2 == 1){
				print("*");
			}
			// 짝수 번째
			else{
				print(" ");
			}
		}
	}
 
	// 짝수 행
	else{
		for(int j = 1; j <= N; j++){
			// 홀수 번째
			if(j % 2 == 1){
				print(" ");
			}
			// 짝수 번째
			else{
				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();
		in.close();
 
		for(int i = 1; i <= 2*N; i++){
 
			// 홀수 행
			if(i % 2 == 1){
				for(int j = 1; j <= N; j++){
					// 홀수 번째
					if(j % 2 == 1){
						System.out.print("*");
					}
					// 짝수 번째
					else{
						System.out.print(" ");
					}
				}
			}
 
			// 짝수 행
			else{
				for(int j = 1; j <= N; j++){
					// 홀수 번째
					if(j % 2 == 1){
						System.out.print(" ");
					}
					// 짝수 번째
					else{
						System.out.print("*");
					}
				}
			}
			System.out.print("\n");
 
		}
 
 
	}
}

 

가장 기본적인 방법이다.

그리고 무의식 중에 내부 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 = 1; i <= 2*N; i++){
 
			// 홀수 행
			if(i % 2 == 1){
				for(int j = 1; j <= N; j++){
					// 홀수 번째
					if(j % 2 == 1){
						System.out.print("*");
					}
					// 짝수 번째
					else{
						System.out.print(" ");
					}
				}
			}
 
			// 짝수 행
			else{
				for(int j = 1; j <= N; j++){
					// 홀수 번째
					if(j % 2 == 1){
						System.out.print(" ");
					}
					// 짝수 번째
					else{
						System.out.print("*");
					}
				}
			}
			System.out.print("\n");
 
		}
 
	}
}

---

- 방법 3 

 

좀 더 괜찮은 방법은 없을까?

 

우리는 출력 부분에서 잘 보면 첫 행과 두번 째 행을 하나의 문자열로 묶으면 해당 문자열만 N 번 출력하면 되기 때문에 반복과정을 엄청나게 줄일 수 있다는 것을 알 수 있다.

 

아래 이미지를 한 번 보자.

 

 

 

 

 

 

 

즉, 우리는 저 두 줄만 문자열로 묶을 수 있다면 묶은 문자열만 반복 출력하면 되는 것이다.

 

그럼 문자열로 어떻게 묶을 것인가?

이에 대한 해답은 바로 StringBuilder 다.

 

StringBuilder 에 첫 번째 행과 두 번째 행을 하나의 문자열로 만든 뒤, 저장된 문자열을 String str 에 저장한다.

그리고 str 을 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++) {
			if(i%2 == 0) {
				sb.append('*');
			}
			else {
				sb.append(' ');
			}
		}
		sb.append('\n');
 
		// 두 번째 행
		for(int i = 0; i < N ; i++) {
			if(i%2!=0) {
				sb.append('*');
			}
			else {
				sb.append(' ');
			}
		}
		sb.append('\n');
		
 
		// sb 에 저장된 문자열을 String 변수에 저장
		String str = sb.toString();
        
		// sb 에 str 을 N-1 번 반복 저장
		for(int i = 1; i < N ; i++) {
			sb.append(str);
		}
		
		System.out.println(sb);
	}
 
}

 

이러면 기존에 이중 for문으로 수행시간이 O(N^2) 이었던 알고리즘이 N 번으로 매우 줄어들게 된다.

또한 출력 메소드를 반복하지 않으니 출력부분에서도 시간이 단축된다.

---

• 성능 차이

위에서 부터 순서대로

 

채점 번호 : 18444791  -  BufferedReader + StringBuiler

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

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

시간을 보면 BufferedReader 와 Scanner 의 성능차이가 난다는 것을 볼 수 있다.

또한 출력 방법과 알고리즘을 다르게 짜니까 엄청나게 시간을 단축시킨 다는 것도 볼 수 있다.

 

---

• 정리

이러한 문제는 사실 엄청 어려운 문제는 아니었던 것 같다.

우리가 어떻게 알고리즘을 짜냐에 따라 수행시간도 천차만별 달라진다.

 

즉 우리는 문제를 볼 때 '규칙성'을 찾아 최소한의 반복문을 사용할 줄도 알아야 한다는 것을 명심해야한다.