๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค[Java] - ์‚ผ๊ฐ ๋‹ฌํŒฝ์ด

by ์ฃผ๋ฐœ2 2020. 9. 26.
๋ฐ˜์‘ํ˜•

programmers.co.kr/learn/courses/30/lessons/68645

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์‚ผ๊ฐ ๋‹ฌํŒฝ์ด

5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

programmers.co.kr

 

 

 

 

์ฝ”๋“œ

class Solution {
	public static int[] solution(int n) {
		if(n == 1) {
			return new int[] {1};
		}

		int answerLen = 3;
		for(int i=3; i<=n; i++) {
			answerLen += i;
		}
		int[] answer = new int[answerLen];

		int[][] arr = new int[n][n];
		int count = 1;	// ๋ฐฐ์—ด ๊ฐ’
		int row = -1;	// ์„ธ๋กœ
		int col = 0;	// ๊ฐ€๋กœ
		int answerIndex = 0;	

		while(true) {
			// โ†“ ๋ฐฉํ–ฅ(row ์ฆ๊ฐ€)
			for(int i=0; i<n; i++) {
				row += 1;
				arr[row][col] = count;
				count ++;
			}
			n --;
			if(n == 0) {
				break;
			}

			// โ†’ ๋ฐฉํ–ฅ(col ์ฆ๊ฐ€)
			for(int i=0; i<n; i++) {
				col += 1;
				arr[row][col] = count;
				count ++;
			}
			n --;
			if(n == 0) {
				break;
			}

			// โ†– ๋ฐฉํ–ฅ(row, col ๊ฐ์†Œ)
			for(int i=0; i<n; i++) {
				row -= 1;
				col -= 1;
				arr[row][col] = count;
				count ++;
			}
			n --;
			if(n == 0) {
				break;
			}
		}

		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				if(arr[i][j] == 0) {	// ๊ฐ row์—์„œ ๊ฐ’์ด ์—†์„๊ฒฝ์šฐ => break
					break;
				}
				answer[answerIndex] = arr[i][j];
				answerIndex ++;
			}
		}
		return answer;
	}

}

ํ’€์ด

๊ธฐ์กด์— ์‚ฌ๊ฐํ˜• ๋‹ฌํŒฝ์ด ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•œ ์‚ผ๊ฐํ˜• ๋‹ฌํŒฝ์ด ๋ฌธ์ œ์ด๋‹ค.

 

์ด ์‚ผ๊ฐํ˜• ๋‹ฌํŒฝ์ด ๋ฌธ์ œ๋Š” ๊ทœ์น™์„ ์ฐพ๋Š”๊ฒƒ์ด ์šฐ์„ ์ด๋‹ค. ์‚ฌ๊ฐํ˜• ๋‹ฌํŒฝ์ด์™€ ๋น„์Šทํ•œ๋ฐ ๋‚ด๊ฐ€ ์ฐพ์€ ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

n=4 ์ผ๋•Œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ณด์ž.

 

์œ„์™€ ๊ฐ™์€ ์‚ผ๊ฐํ˜•์„ 

 

์œ„์™€ ๊ฐ™์€ ์ด๋“ฑ๋ณ€ ์‚ผ๊ฐํ˜•์œผ๋กœ ๋ณด๊ณ , ๊ฐ ๋ฐฉํ–ฅ๋Œ€๋กœ ๊ฐ’์„ ์ฑ„์›Œ ๋ฐฐ์—ด์— ๋‹ด์•„์„œ ๋ฆฌํ„ดํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

 

โ†“ , โ†’ , โ†– ๊ฐ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐˆ ๋•Œ๋งˆ๋‹ค, ๋ฐ˜๋ณต๋˜๋Š” ํšŸ์ˆ˜๊ฐ€ 1ํšŒ์”ฉ ์ค„์–ด๋“ ๋‹ค.

 

4ํšŒ ๋ฐ˜๋ณต โ†“ 

3ํšŒ ๋ฐ˜๋ณต  โ†’ 

2ํšŒ ๋ฐ˜๋ณต โ†–

1ํšŒ ๋ฐ˜๋ณต โ†“

0ํšŒ ๋ฐ˜๋ณต (๋)

 

๋”ฐ๋ผ์„œ, ์ž…๋ ฅ๋ฐ›์€ n์ด 0์ด ๋ ๋•Œ๊นŒ์ง€, โ†“ , โ†’ , โ†– ๋ฐฉํ–ฅ์œผ๋กœ ์ง„ํ–‰ํ•˜๋ฉด์„œ 2์ฐจ์› ๋ฐฐ์—ด์— ๊ฐ’์„ ์ฑ„์šฐ๊ณ ,

๊ฐ ๋‹จ๊ณ„๊ฐ€ ๋๋‚ ๋•Œ๋งˆ๋‹ค n์„ ๊ฐ์†Œ์‹œํ‚จ๋‹ค.

 

๊ฐ ๋‹จ๊ณ„๋งˆ๋‹ค row, col ๊ฐ’์ด ์ฆ๊ฐ€ํ•˜๊ฑฐ๋‚˜ ๊ฐ์†Œํ•˜๋Š”๋ฐ, ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

โ†“ ๋ฐฉํ–ฅ:  row(ํ–‰) 1์”ฉ ์ฆ๊ฐ€

			// โ†“ ๋ฐฉํ–ฅ(row ์ฆ๊ฐ€)
			for(int i=0; i<n; i++) {
				row += 1;
				arr[row][col] = count;
				count ++;
			}

 

โ†’ ๋ฐฉํ–ฅ:  col(์—ด) 1์”ฉ ์ฆ๊ฐ€

			// โ†’ ๋ฐฉํ–ฅ(col ์ฆ๊ฐ€)
			for(int i=0; i<n; i++) {
				col += 1;
				arr[row][col] = count;
				count ++;
			}

 

โ†– ๋ฐฉํ–ฅ: row(ํ–‰), col(์—ด) 1์”ฉ ๊ฐ์†Œ

			// โ†– ๋ฐฉํ–ฅ(row, col ๊ฐ์†Œ)
			for(int i=0; i<n; i++) {
				row -= 1;
				col -= 1;
				arr[row][col] = count;
				count ++;
			}

 

์œ„์™€ ๊ฐ™์€ ๊ทœ์น™์— ๋”ฐ๋ผ ๊ฐ ๋‹จ๊ณ„์˜ for๋ฌธ์—์„œ row, col ๊ฐ’์„ ๋ณ€๊ฒฝ์‹œ์ผœ์ค€๋‹ค.

 

* ์ฒ˜์Œ row์˜ ๊ฐ’์„ -1๋กœ ์ •ํ•œ ์ด์œ ๋Š”, ๋งŒ์•ฝ row ๊ฐ’์„ 0์œผ๋กœ ์ง€์ •ํ• ๊ฒฝ์šฐ,

์ฒซ for๋ฌธ์ด ๋๋‚œ ๋’ค์˜ row ๊ฐ’์€ n+1์ด ๋˜์–ด ์ธ๋ฑ์Šค์˜ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๊ฒŒ๋œ๋‹ค.

 

* ์ฒ˜์Œ์— ๋ฆฌํ„ดํ•  ๋ฐฐ์—ด answer์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•ด์•ผํ•˜๋Š”๋ฐ, ์ด๊ฒƒ๋„ ์ž…๋ ฅ๋ฐ›๋Š” n์— ๋”ฐ๋ผ ๊ทœ์น™์ด ์ •ํ•ด์ง„๋‹ค.

n , ์ˆซ์ž์˜ ์ด ๊ฐฏ์ˆ˜์— ๋”ฐ๋ฅธ ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

n ์ˆซ์ž์˜ ๊ฐฏ์ˆ˜(๋ฐฐ์—ด์˜ ๊ธธ์ด)
2 3   (+0)
3 6   (+3)
4 10  (+4)
5 15  (+5)
6 21  (+6)

 

์œ„ ๊ทœ์น™์— ๋”ฐ๋ผ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋Š” i๊ฐ€ 3๋ถ€ํ„ฐ, ์ž…๋ ฅ๋ฐ›์€ n๊นŒ์ง€ i๊ฐ’(3, 4, 5, ...)์„ ๋”ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

		int answerLen = 3;
		for(int i=3; i<=n; i++) {
			answerLen += i;
		}

 

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€

๐Ÿ”HALO