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
[문제 설명]
정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상 1,000 이하입니다.
입출력 예
| 4 | [1,2,9,3,10,8,4,5,6,7] |
| 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] |
[풀이]
내가 생각한 풀이 방법은 주어진 로직대로 푸는 방법이었는데, 일단 피라미드를 배열화 시키는 아이디어가 필요했다.
위 그림과 같이 주어진 피라미드 형태의 도형들을 배열의 형식으로 바꿔주면 된다.
그 다음 아이디어는 주어진 조건의 패턴이다.
이처럼 아무리 n이 크더라도 3가지의 조건의 패턴을 바뀌지 않는다. 그림에서 9까지 작성한 다음 아래로 뻗는 화살표 처럼 i가 증가한 다음 10이 저장될 것이다.
여기서 중요한 포인트가 있다. 첫 번째 아래 화살표는 4번, 오른쪽 화살표는 3번, 대각선 왼쪽 화살표는 2번, 다시 아래 화살표는 1번의 반복으로 배열의 값이 정해졌다.
이 그림은 n = 4일 때이다. 결론적으로 이 문제의 반복 패턴은 n, n-1, n-2, n-3이 1과 같을 때까지 반복해주면 되는 것이다.
[코드]
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
public int[] solution(int n) {
int[][] pyramid = new int[n][n]; // 이차원 배열 선언
int status = 0; // 0 : 아래로 내려가는 방향, 1 : 오른쪽으로 가는 방향, 2: 대각선 위로 올라가는 방향
int number = 0; // 1부터 넣어줄 번호
int i = 0;
int j = 0;
for (int k = n; k >= 1; k--) { // k = n
if (status == 0) {
for (int t = 0; t < k; t++) {
pyramid[i++][j] = ++number;
}
status++; // 0다음에는 1의 상태가 유지되어야한다.
i--; // 위에서 i++로 1커진 i를 다시 -1해주는 것
j++;
} else if (status == 1) {
for (int t = 0; t < k; t++) {
pyramid[i][j++] = ++number;
}
j--; // 마지막 유지
i--; // 대각선 시작
j--;
status++;
} else {
for (int t = 0; t < k; t++) {
pyramid[i--][j--] = ++number;
}
i++; // 마지막 유지
j++;
i++; //0으로 초기화. i가 한칸 아래여야한다.
status = 0;
}
}
ArrayList<Integer> result = new ArrayList<Integer>();
for (int[] arr : pyramid) { //0이 아니면 넣기
for (int e : arr) {
if(e != 0) {
result.add(e);
}
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
|
cs |
느낀 점: 처음에는 피라미드 형태로 규칙을 정해서 푸는 방법을 생각해봤지만 생각이 나질않아 주어진 조건을 이용해서 문제풀이를 했다. 나름 재밌는 문제였던 것 같다.