programmers.co.kr/learn/courses/30/lessons/68645
์ฝ๋
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;
}
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค[Java] - H-Index(์ ๋ ฌ) (0) | 2020.12.05 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค[Java] - ํคํจ๋ ๋๋ฅด๊ธฐ(2020 ์นด์นด์ค ์ธํด์ญ) (1) | 2020.10.03 |
[Programmers] - ๋ ๊ฐ ๋ฝ์์ ๋ํ๊ธฐ (0) | 2020.09.20 |
[SW Expert Academy] - (D2)1974. ์ค๋์ฟ ๊ฒ์ฆ (0) | 2020.08.10 |
[SW Expert Academy] - (D1)1933. ๊ฐ๋จํ N์ ์ฝ์(Stream) (0) | 2020.08.09 |
๋๊ธ