function solution(n) {
const arr = Array(n).fill()
for (let i = 0; i < n; i += 1) {
arr[i] = (Array(i + 1).fill(-1))
}
let idx = 1
let [cx, cy] = [-1, 0] // 시작점 (current x, current y)
while (arr.flat().includes(-1)) {
while (cx + 1 < n && arr[cx + 1][cy] === -1) { // 밑으로 이동
cx += 1
arr[cx][cy] = idx++
}
while (cy + 1 < n && arr[cx][cy + 1] === -1) { // 오른쪽 이동
cy += 1
arr[cx][cy] = idx++
}
while (cx - 1 >= 0 && arr[cx - 1][cy - 1] === -1) { // 위로 이동
cx -= 1
cy -= 1
arr[cx][cy] = idx++
}
}
return arr.flat()
}
뒤에 몇가지 케이스에서 타임 오버가 우수수 나왔습니다. 개인적인 추측으로는 while 조건식 안이 의심되었는데 해당 부분은 피라미드에 빈 값(-1)이 있는지 확인하는 부분입니다. flat의 정확한 시간복잡도는 모르겠지만 n 정도일 것 같은데 2차원 배열을 flat하면 2번 시도해서 아마 n^2이 걸리는 것 같습니다. 그래서 총 n^3의 복잡도가 발생하여 시간이 오버된게 아닐까 생각합니다.
작성 코드 (2차 시도 / 통과)
function solution(n) {
if (n === 1) return [1];
if (n === 2) return [1, 2, 3];
const arr = Array(n).fill();
for (let i = 0; i < n; i += 1) {
arr[i] = Array(i + 1).fill(-1);
}
let idx = 1;
let [cx, cy] = [-1, 0];
while (1) {
if ( // 더 이상 빈 값이 없는 경우
arr[cx + 1][cy] !== -1 &&
arr[cx][cy + 1] !== -1 &&
arr[cx - 1][cy - 1] !== -1
)
break;
while (cx + 1 < n && arr[cx + 1][cy] === -1) {
cx += 1;
arr[cx][cy] = idx++;
}
while (cy + 1 < n && arr[cx][cy + 1] === -1) {
cy += 1;
arr[cx][cy] = idx++;
}
while (cx - 1 >= 0 && arr[cx - 1][cy - 1] === -1) {
cx -= 1;
cy -= 1;
arr[cx][cy] = idx++;
}
}
return arr.flat();
}
조건식을 살짝 다른방식으로 바꿨습니다. 현재 위치에서 위, 아래, 오른쪽에 더이상 빈 값이 없는 경우 루프를 끝내주면 됩니다. 그러면 조건식은 1의 복잡도를 가지니 총 n^2의 복잡도로 구현할 수 있습니다.
구현 로직
이 문제는 전형적인 구현 문제입니다. 특별한 코딩 기법은 생각나지 않아서 우직하게 풀어가는 방식으로 작성했습니다. 먼저 피라미드를 만들어주고 빈 값을 의미하는 -1로 초기화해줍니다. 그리고 각각 아래, 오른쪽, 위쪽으로 이동해가며 인덱스 값을 넣어주는데 위쪽 부분은 배열이 좁아지니 x, y값이 모두 1씩 줄어들도록 구현해줍니다. 더 이상 주변에 -1이 없는 경우 루프를 끝내고 피라미드를 1차원으로 만들어 리턴하면 됩니다.