프로그래머스 - Lv.2 삼각달팽이 JS

https://school.programmers.co.kr/learn/courses/30/lessons/68645

이 문제는 2차원의 배열에 반시계 방향으로 숫자를 채운 뒤, 배열 순서대로 숫자를 반환하는 문제다.

 

처음 문제를 보았을 때는 풀지 못했던 문제인데, 백준에서 다양한 알고리즘 풀이 방식에 대해 공부하게 되면서 풀 수 있게 되었다.

 

생각한 로직은 다음과 같다.

먼저 다음과 같은 2차원 배열을 생성한다. 이때, 해당 배열은 삼각형 형태를 띄어야하므로, 인덱스에 따라 커지게 만들었다.

이후 하, 우, 좌상으로 이동하며 빈칸을 채우는 로직을 구현한다. 이때 해당 칸이 채워져 있을 경우나, 범위를 벗어나는 경우 이를 처리할 수 있는 함수도 함께 구현한다. (BFS나 DFS에서 사용하는 방식을 응용하였다)

 

구현한 코드는 다음과 같다.

function solution(n) {
  // 위에서 언급한 삼각형 꼴 2차원 배열 생성 로직
  // boolean을 활용한 조건문을 사용하기 쉽게 초기값은 0으로 할당
  const arr = Array.from({length : n}, (_,idx)=> {
    return Array.from({length : idx+1}, ()=> 0)
  })

  // 삼각형의 크기를 구하는 로직인데,
  // 지금보니 (n * n+1)/2 로 구현하는 것이 더 간단할 듯
  let triangleSize = 0
  for(let i = 1 ; i <= n ; i++) triangleSize += i

  // 좌표 위치가 내가 원하는 범위 내에 있는지 검증하기 위한 함수
  const verify = (x,y) => {
    return x >= 0 && y >= 0 && n > x && n > y
  }

  // 시작 위치
  let location = [0,0]
  // 하, 우, 좌상 위치를 쉽게 사용하기 위한 방향 배열과 인덱스 변수
  const direction = [[0,1],[1,0],[-1,-1]]
  let directionIdx = 0
  
  // 삼각형 크기만큼 반복하는 반복문
  for(let i = 0 ; i < triangleSize ; i ++) {
    // location 변수에서 받아온 좌표를 배열에 i + 1로 할당
    const [x,y] = location
    arr[y][x] = i + 1
	
    // 다음 좌표가 접근 가능한지 구한 뒤 location 변수에 새로 할당하는 로직
    const [dx, dy] = direction[directionIdx%3]
    const [nx, ny] = [dx + x, dy + y]
	
    // 기존 진행 방향대로 산출한 다음 좌표가 검증에 통과했을 경우, location 변수에 새로 할당
    // 이때 검증은 위에서 언급한 바와 같이, 좌표가 정상적인지 & 이미 해당 좌표가 채워져 있는지를 검증
    if(verify(nx, ny) && !arr[ny][nx]) location = [nx, ny]
    else {
    // 기존 진행 좌표가 조건을 만족하지 못할 경우, 다음 이동방향으로 수정하여 진행한 뒤 할당
      const [dx, dy] = direction[++directionIdx%3]
      const [nx, ny] = [dx + x, dy + y]
      location = [nx, ny]
    }
  }
  
  // 2차원 배열을 1차원으로 수정하는 flat 메서드를 활용하여 리턴
  return arr.flat()
}