본문으로 바로가기

모래시계 알고리즘

category 컴퓨터/알고리즘 2016. 6. 20. 09:44
안녕하세요? QRD입니다.
인터넷에 많이 떠도는 문제 위주로 발췌해서 스스로 한 번 풀어보고 공유하는 거라 정확한 답이 될 순 없어요.
혹시 제가 구현한 것보다 더 쉽고 괜찮은 알고리즘으로 해결하신다면 공유 좀 부탁드립니다.
문제 나갑니다.
12345
06780
00900
01011120
1314151617

위와 같은 모양으로 숫자를 출력해 보세요.

오늘은 모래시계 모양으로 숫자를 출력해 보겠습니다.
마찬가지로 무궁무진한 코딩 방법이 존재하겠지만, 저는 아래와 같이 코딩하였습니다.

package test;
import java.util.Scanner;
public class test {

public static void main(String args[]) {
	rhombusAlgorithm();
}
public static boolean rhombusAlgorithm(){
		Scanner scan = new Scanner(System.in);
		int length = scan.nextInt();
		int [][]matrix = new int [length][length];
		int cnt = 1; // 숫자
		int x = -1; // 가로
		int y = 0; // 세로 
		int y2 = -1; // 현재 줄에서 y가 시작된 위치 저장
		int direct = -2; // 행에서 몇개의 숫자를 찍어줘야 하는 갯수를 length에다 더해준다.
		int upDownCheck = 1; //다음 행의 찍어내야 할 숫자의 증감을 알기 위한 Flag
		
		while(true){
			for (int i = 0; i < length; i++) {
				x = x + 1;
				matrix[y][x] = cnt;
				cnt ++ ;
			}
			
			if(length-1 == 1 || length== 1){
				upDownCheck = 0;
				direct = direct * -1;
			}
			
			if(upDownCheck == 1){
				length= length + direct;
				y2 = y2 + 1;
				x = y2;
				y ++ ;
			}
			else{
				length= length + direct;
				y2 = y2 - 1;
				x = y2;
				y++;
			}
			if(length> matrix.length){
				printMatrix(matrix);
				return false;
			}
		}
	}
	/**
 	* 2차원 배열을 출력해주는 메서드
 	* @param matrix
	*/
	public static void printMatrix(int matrix[][]) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println("\n");
		}
	}
}
실행 후 맨 처음 원하는 정사각형의 크기를 입력합니다.(ex. 5)
모래시계 알고리즘을 잘 살펴보면,
처음에는 정사각형 크기의 2씩 순차적으로 숫자를 찍어내는 갯수가 작아지다가, 다시 증가하는 것을 알 수 있다.
upDownCheck 변수는 숫자를 찍어내는 갯수가 감소하는지 증가하는지 알기 위한 Flag이고,
y2는 가로의 시작점을 저장하기 위한 변수,
direct는 이 전 행에서 찍어낸 숫자의 길이에 더함으로써, 이번 행에서 찍어내야 할 숫자의 갯수입니다.
나머지는 알고리즘을 분석해 보시기 바랍니다.
감사합니다. QRD였습니다. 꾸벅(_ _)

'컴퓨터 > 알고리즘' 카테고리의 다른 글

개미수열 알고리즘  (1) 2016.06.22
달팽이 알고리즘  (0) 2016.06.15