BOJ 1022 소용돌이예쁘게출력하기 Java

BOJ 1022 소용돌이예쁘게출력하기 Java

 

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

1022번: 소용돌이 예쁘게 출력하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1022_소용돌이예쁘게출력하기 {
	int[][] grid;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int r1 = Integer.parseInt(st.nextToken());
		int c1 = Integer.parseInt(st.nextToken());
		int r2 = Integer.parseInt(st.nextToken());
		int c2 = Integer.parseInt(st.nextToken());
		
		new BOJ_1022_소용돌이예쁘게출력하기().solution(r1, c1, r2, c2);
		
	} // main
	
	void makeArr(int r1, int c1, int r2, int c2) {
		int[][] dir = new int[][] { {0, 1},{-1, 0},{0, -1},{1, 0} };
		int r = 0, c = 0, n = 1, cnt = 2, number = 1, d = 0;
		if(r1 <= r && r <= r2 && c1 <= c && c <= c2)
			grid[r-r1][c-c1] = number;
		
		while(true) {
			if(r < -5000 || c < -5000 || r > 5000 || c > 5000) break;
			
			if(cnt == 0) {
				cnt = 2;
				n++;
			}
			
			for (int k = 0; k < n; k++) {
				if(r1 <= r && r <= r2 && c1 <= c && c <= c2)
					grid[r-r1][c-c1] = number;
				number++;
				r += dir[d][0];
				c += dir[d][1];
				if(r < -5000 || c < -5000 || r > 5000 || c > 5000) break;
			}
			d = (d+1)%4;
			cnt--;
		}
		
	}
	
	void solution(int r1, int c1, int r2, int c2) {
		grid = new int[r2-r1+1][c2-c1+1];
		makeArr(r1, c1, r2, c2);
		
		int maxLen = 0;
		for (int i = 0; i <= r2-r1; i++) {
			for (int j = 0; j <= c2-c1; j++) {
				int len = Integer.toString(grid[i][j]).length();
				if(maxLen < len) {
					maxLen = len;
				}
			}
		}
		
		for (int i = 0; i <= r2-r1; i++) {
			for (int j = 0; j <= c2-c1; j++) {
				System.out.format("%" + maxLen + "d ", grid[i][j]);
			}
			System.out.println();
		}
		
	}
}

 

 

 

오랜만에 시간이 오래걸리는 알고리즘을 풀었다. 소용돌이는 삼성에 자주 나오는 유형인듯

처음에 메모리 신경 안 쓰고 0~10001 까지 다 구했더니 메모리 초과...

그래서 다시 푼 코드는

 

먼저 0~r2-21+1 , 0~c2-c1+1 까지 배열을 만들어서

그 사이에 포함되는 애들만 값을 넣어서 출력하는 것이다.

 

 

먼저 소용돌이는 매번 방향이 →↑←↓ 을 바꿔가면서 1칸이동,1칸이동,2칸이동,2칸이동 이렇게 2번씩 반복한다.

int n, cnt, number, d 

변수가 4개 있는 이유다.

 

소용돌이를 진행하면서

if(r1 <= r && r <= r2 && c1 <= c && c <= c2)
         grid[r-r1][c-c1] = number;

 

이렇게 r1 r2 c1 c2가 출력해야할 배열인데, 이 사이에 r c 가 존재하면 [r-r1][c-c1]에 값을 넣어준다.

즉 r이 -3~3 일 때

-3을 0이라고 생각하고 0~6 까지라고하면 쉽다.

 

이런식으로 만든 배열안에 속하는 숫자만 배열에 입력하고

 

마지막에 출력할 때는 배열에서 가장 큰 숫자 길이를 Integer.toString().length() 로 구하여

System.out.format 로 "%가장긴길이d "  출력!