- 밑변의 길이와 높이가 n인 삼각형 : 위에서부터 1~n의 길이를 가진 n개의 배열 형태
- 달팽이 채우기 : 맨 위 꼭짓점부터 반시계 방향으로
- 최종 출력 : 첫 행부터 마지막 행까지 모두 순서대로 합친 배열
2. 전략
(1) 자료구조 (3번에서 더 쉬운 자료구조로 변경할 것)
- Lend 클래스 : 각 행의 정보를 담은 클래스를 생성
[멤버 변수] - int size : 행 번호 = 행의 길이 - int[] line : 행의 요소를 담은 배열
[생성자] int 매개변수 n을 받아 size에 대입 & line을 할당(length를 size로 하는)
[메소드] - public void putNum(int i, int n) : line의 i번째 수에 n을 대입 - public int getNum(int i) : line의 i번째 수를 출력
- ArrayList<Line> list : n개의 Lend 객체를 관리하는 ArrayList
(2) 시뮬레이션 : 달팽이 채우기
① 관리해야할 변수
- start, end : 시뮬레이션 대상이 되는 시작 행의 번호, 끝 행의 번호
- num : 달팽이 채우기의 대상이 되는 수(하나 채울 때마다 증가)
- index : 각 행의 채울 대상 인덱스를 정하기 위한 변수
② 프로세스
※ 3개의 작업을 마치면 탐색을 완료한 행을 배제하기 위해 start와 end를 조정할 것 (단, start <= end일 때까지) 1. 아래 방향으로 각 행의 가장 왼쪽 요소(index번째)에 달팽이 채우기 2. 마지막 행을 전부 채우기(index+1 ~ end-index-1) 3. 윗 방향으로 각 행의 가장 오른쪽 요소(i-index번째)에 달팽이 채우기 모두 수행 후 start는 2행 내려오며, end는 1행 올라간다. 가장자리가 채워졌으므로 index는 1 증가시킨다.
(3) 최종 출력 : 순차적으로 탐색
ArrayList의 각 Line 객체에 대해서 순차적으로 getNum의 결과를 answer 배열에 담기
3. 참고사항
(1) 자료 구조 변경 : N x N 2차원 배열
수직 이등변 삼각형으로 간주하고 풀어도 시뮬레이션 프로세스는 그대로 적용할 수 있다!
클래스 ArrayList일 때보다 훨씬 간단한 자료 구조 사용
▶ 좀 더 유연한 사고 능력을 가지자!!
(2) 시간 복잡도 : 3n + 3(n-3) + ... => O(n^2)
4. 코드
(수정 전 코드 _ 2 기반)
import java.util.*;
class Solution {
public int[] solution(int n) {
int[] answer = new int[n*(n+1)/2];
//구성 : Line ArrayList
ArrayList<Line> list = new ArrayList<>();
for(int i = 0; i < n; i++){
list.add(new Line(i+1));
}
//탐색 : 순서대로 숫자 넣기
int start = 0; int end = n-1;
int num = 1; int index = 0;
while(start <= end){
for(int i = start; i <= end; i++){ //0+index
if(list.get(i).getNum(index) == 0) list.get(i).putNum(index, num++);
}
for(int i = index+1; i < end-index; i++){ //endline
if(list.get(end).getNum(i) == 0) list.get(end).putNum(i, num++);
}
for(int i = end; i >= start; i--){ //end-index
if(list.get(i).getNum(i-index) == 0) list.get(i).putNum(i-index, num++);
}
start += 2; end -= 1;
index+=1;
}
//결과 - ArrayList에 따라 결과 도출
index = 0;
for(int i=0; i < list.size(); i++){
Line line = list.get(i);
for(int j = 0; j < i+1; j++) answer[index++] = line.getNum(j);
}
return answer;
}
class Line{
int size = 0;
int[] line = {};
Line(int n){
this.size = n;
this.line = new int[size];
}
public void putNum(int i, int n){
line[i] = n;
}
public int getNum(int i){
return line[i];
}
}
}
(수정 후 코드 _ 3-(1) 적용)
import java.util.*;
class Solution {
public int[] solution(int n) {
int[] answer = new int[n*(n+1)/2];
//구성
int[][] list = new int[n][n];
//탐색 : 순서대로 숫자 넣기
int start = 0; int end = n-1;
int num = 1; int index = 0;
while(start <= end){
for(int i = start; i <= end; i++){ //0+index
list[i][index] = (list[i][index] == 0) ? num++ : list[i][index];
}
for(int i = index+1; i < end-index; i++){ //endline
list[end][i] = (list[end][i] == 0) ? num++ : list[end][i];
}
for(int i = end; i >= start; i--){ //end-index
list[i][i-index] = (list[i][i-index] == 0) ? num++ : list[i][i-index];
}
start += 2; end -= 1;
index+=1;
}
//결과
index = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i+1; j++) answer[index++] = list[i][j];
}
return answer;
}
}
