Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- dp문제
- reactNative
- ESP8266WiFi
- 백준문제풀이 #백준 #백준문제 #스타트택시
- CSS
- peap
- 이친수문제
- C
- 연결리스트
- 포인터
- aspect-ratio
- 백준풀이
- 아두이노 우노
- 2193
- 프로젝트초기설정
- scss
- 백준 #백준2661 #좋은수열 #Java #코딩
- ESP8266
- 백준java
- CSS Flex
- 백준
- 백준15988풀이
- 리액트네이티브
- @supports
- ESP-01WiFi
- 노마드코더
- ESP-01
- Flexible box
- 백준자바
- scroll-snap
Archives
- Today
- Total
코딩 농장
[백준 2448번/JAVA] 별 찍기 - 11 (문제 풀이, 코드) 본문
728x90
별 찍기 -11
예제는 아래와 같다.
[문제]
N = 3 * 2^k 이다. N번째 줄까지 위와 같은 규칙으로 별을 찍어야한다.
[풀이]
별 찍기 문제는 항상 규칙을 찾는 문제다. 어떤 규칙을 찾느냐에 따라 코드가 달라질 것 같다.
나는 아래와 같은 규칙을 찾았다.
- 내가 정한 삼각형은 3줄이다.
- 가장 윗 줄의 가운데에 별 하나(위 꼭짓점)
- 두 번째 줄 가운데 칸을 비우고 양 옆으로 별 하나
- 마지막 줄은 별 5개. 내가 만들 삼각형의 기준은 아래 그림과 같다.
- 그리고 삼각형의 아래 왼쪽 꼭짓점, 아래 오른쪽 꼭짓점 밑 줄의 옆 칸으로부터 새로운 삼각형이 시작된다.
- 단, 아래와 같은 경우는 삼각형의 꼭지점이더라도 만들어질 수 없다.
- 삼각형 밑변의 꼭짓점에서부터 ±2칸 사이에 다른 삼각형의 꼭짓점이 발견되면 해당 꼭짓점으로부터 삼각형이 생성되는 것은 불가능하다!
[내 코드 알고리즘]
- 별과 ' '(빈칸)을 넣을 2차원 배열을 만들었다.
- 모든 칸은 빈칸으로 초기화한다.
- 2차원 배열의 행은 N, 열은 2*N-1
- 열의 경우 k에 1,2,3을 대입하여 규칙을 찾아냈다.
- 이하 star[N][2*N-1]로 부르도록 하겠다.
- 첫 삼각형은 탐색할 꼭짓점이 없으므로 직접 만든다.
- make(0,N-1) 메서드를 사용했다. 해당 메서드는 아래와 같이 동작한다.
- star[0][N-1] = '*'; 0번째 줄의 N-1칸 자리에 삼각형의 가장 위쪽 꼭짓점을 찍는다.
- star[1][N-2] = '*'; star[1][N] = '*'; 1번째 줄의 N-2, N자리에 별을 찍는다.
- star[2][N-3]~[N+2] = '*'; 5개 별 찍는다.
- 위에 정의했던 삼각형을 찍는 메서드다.
- 삼각형의 아래 꼭짓점이 어딘지 탐색한다.
- find(3,N-3) 메서드를 사용했다. 해당 메서드는 아래와 같이 동작한다.
- 3번째 줄의 윗 줄인 2번째 줄에서 N-3번째 칸이 *인지 확인한다.
- *이라면 왼쪽 칸이 ' '인지 확인한다.
- 왼쪽 칸이 ' '라면 해당 삼각형의 왼쪽 꼭짓점을 찾았다!
- 해당 위치보다 2칸 왼쪽에 *이 있는지 확인한다(이 경우는 삼각형을 만들 수 없다.)
- 없다면 make(3,N-4) // 3번째줄의 N-4칸에 '*'을 찍어야하니까!
- 만약 왼쪽 꼭짓점이 아니었다면 오른쪽 꼭짓점도 비슷하게 확인한다!
- 해당 칸이 꼭짓점이 아닌 칸이라면 +1을 해서 다음 칸을 확인한다.
- find(3,N-3)을 할 때, 왼쪽 꼭짓점을 알려주는 방식으로 하려고 parameter를 두 개 받았으나, 이 경우 한 쪽으로만 치우친 삼각형이 만들어져서 첫 삼각형 다음부터는 find(a,0)을 사용한다.
- 해당 줄의 꼭짓점 탐색이 모두 끝났다면 find(6,0)
- 만약 6==N이면 종료한다.
- StringBuilder에 star 2차원 배열의 값을 다 담아서 출력한다.
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class stareleven_2448 {
static int N;
static char[][] star;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
star = new char[N][N*2-1];
for(int i=0; i<N; i++)
for(int j=0; j<N*2-1; j++)
star[i][j] = ' ';
/* 첫 삼각형만 예외로 미리 만들어서 star 에 넣어둠.*/
make(0,N-1);
find(3,N-3);
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
for(int j=0; j<N*2-1; j++)
sb.append(star[i][j]);
sb.append("\n");
}
System.out.println(sb);
}
public static void find(int a, int b) {
if(a>=N) return;
for(int i=0; i<N*2-1; i++) {
if(b+i>=N*2-1) break;
/* 왼쪽 꼭짓점인 경우*/
if(star[a-1][b+i] == '*' && star[a-1][b+i-1] == ' ') {
if(star[a-1][b+i-2] != '*')
make(a,b+i-1);
}
/* 오른쪽 꼭짓점인 경우 */
else if(star[a-1][b+i] == '*' && star[a-1][b+i+1] == ' ') {
if(star[a-1][b+i+2] != '*')
make(a,b+i+1);
}
}
find(a+3,0); // 삼각형의 왼쪽 꼭짓점이 어딘지 알려주기!
}
public static void make(int a, int b) {
// a : 삼각형의 행 시작 위치
// b : 삼각형의 열 시작 위치
star[a][b] = '*';
star[a+1][b-1] = '*';
star[a+1][b+1] = '*';
for(int i=0; i<5; i++)
star[a+2][b-2+i] = '*';
}
}
GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.
https://github.com/MOBUMIN/BJalgorithm/blob/master/stareleven_2448.java
MOBUMIN/BJalgorithm
백준 알고리즘 푼 것. Contribute to MOBUMIN/BJalgorithm development by creating an account on GitHub.
github.com
'백준' 카테고리의 다른 글
[백준 1516번/JAVA] 게임 개발 (문제 풀이, 코드) (0) | 2020.09.26 |
---|---|
[백준 1613번/JAVA] 역사 (문제 풀이, 코드) (0) | 2020.09.20 |
[백준 2580번/JAVA] 스도쿠 (문제 풀이, 코드) (0) | 2020.09.20 |
[백준 2661번/JAVA] 좋은 수열 (문제 풀이, 코드) (0) | 2020.09.15 |
[JAVA/백준 19238번] 스타트택시 (문제풀이, 코드) (0) | 2020.09.06 |
Comments