[프로그래머스] 지게차와 크레인

문제 개요

1부터 n까지 번호가 매겨진 택배 상자들을 창고에 지그재그 패턴으로 배치하고, 특정 상자를 꺼내기 위해 필요한 총 상자 개수를 계산하는 문제다.

문제 조건

• n: 총 택배 상자 개수
• w: 가로로 배치할 상자 개수 (한 행의 너비)
• num: 꺼내려는 상자의 번호

배치 규칙

1. 첫 번째 행: 왼쪽→오른쪽으로 1, 2, 3, ..., w
2. 두 번째 행: 오른쪽→왼쪽으로 w+1, w+2, ..., 2w
3. 세 번째 행: 왼쪽→오른쪽으로 2w+1, 2w+2, ..., 3w
4. 이 패턴을 반복한다.

제약 조건

• 특정 상자를 꺼내려면 그 위에 있는 모든 상자를 먼저 꺼내야 한다.
• 같은 열에 있는 상자들은 세로로 쌓인 구조다.

예시 분석

n=22, w=6일 때 배치:

행 0:  1  2  3  4  5  6
행 1: 12 11 10  9  8  7
행 2: 13 14 15 16 17 18
행 3:       22 21 20 19

8번 상자를 꺼내려면:

• 8번 상자 (행 1, 열 4)
• 17번 상자 (행 2, 열 4)
• 20번 상자 (행 3, 열 4)
• 총 3개 상자 필요

해결 방법

접근 방식

1. 지그재그 패턴 구현: 각 상자의 정확한 위치 계산
2. 위치 추적: 행과 열 정보를 저장
3. 스택 구조 활용: 같은 열의 상자들을 세로로 처리

핵심 알고리즘

function solution(n, w, num) {
  // 각 상자의 위치를 저장할 배열 (행, 열)
  const positions = [];

  // 지그재그 패턴으로 상자 배치
  let currentRow = 0;
  let currentCol = 0;
  let direction = 1; // 1: 왼쪽->오른쪽, -1: 오른쪽->왼쪽

  for (let boxNum = 1; boxNum <= n; boxNum++) {
    // 현재 행이 가득 찼으면 다음 행으로
    if (currentCol >= w) {
      currentRow++;
      currentCol = 0;
      direction *= -1; // 방향 전환
    }

    // 상자 위치 저장 (지그재그 패턴 적용)
    let actualCol = direction === 1 ? currentCol : w - 1 - currentCol;
    positions[boxNum] = { row: currentRow, col: actualCol };

    // 다음 위치로 이동
    currentCol++;
  }

  // 목표 상자의 위치 찾기
  const targetPos = positions[num];
  if (!targetPos) return 0;

  let count = 0;

  // 목표 상자와 같은 열에 있으면서 그 위에 있는 모든 상자 계산
  for (let boxNum = 1; boxNum <= n; boxNum++) {
    const pos = positions[boxNum];
    if (pos && pos.col === targetPos.col && pos.row >= targetPos.row) {
      count++;
    }
  }

  return count;
}

구현 세부사항

1. 지그재그 패턴 구현

let direction = 1; // 방향 변수
// 홀수 행: direction = 1 (왼쪽→오른쪽)
// 짝수 행: direction = -1 (오른쪽→왼쪽)

let actualCol = direction === 1 ? currentCol : w - 1 - currentCol;

2. 위치 계산

• 행 계산: currentRow = Math.floor((boxNum - 1) / w)
• 열 계산: 지그재그 패턴에 따라 방향별로 다르게 계산한다.

3. 스택 구조 처리

// 같은 열에 있으면서 그 위에 있는 모든 상자
if (pos.col === targetPos.col && pos.row >= targetPos.row) {
  count++;
}

시간복잡도 분석

• 시간복잡도: O(n)
  • 각 상자를 한 번씩 순회하여 위치 계산: O(n)
  • 목표 상자와 같은 열의 상자들을 찾는 과정: O(n)
  • 전체적으로 O(n) 시간복잡도다.
• 공간복잡도: O(n)
  • 각 상자의 위치 정보를 저장하는 배열: O(n)

테스트 케이스

n	w	num	예상 결과	설명
22	6	8	3	8, 17, 20번 상자
6	3	1	2	1, 6번 상자
6	3	2	2	2, 5번 상자
6	3	3	1	3번 상자만
12	4	1	3	1, 5, 9번 상자
12	4	4	3	4, 8, 12번 상자

최적화 포인트

1. 불필요한 연산 제거

• 배열의 unshift(), push() 연산 대신 직접 위치 계산
• 복잡한 패딩 로직 제거

2. 메모리 효율성

• 필요한 정보만 저장 (행, 열)
• 불필요한 배열 생성 방지

3. 가독성 향상

• 명확한 변수명 사용
• 단계별 주석 추가

다른 접근법과의 비교

원래 코드 (복잡한 버전)

// 배열 조작을 통한 배치
if (dir === true) {
  lpush.unshift(idx);
} else {
  lpush.push(idx);
}

문제점:

• unshift() 연산이 O(n) 시간복잡도다.
• 복잡한 패딩 로직이다.
• 가독성이 떨어진다.

개선된 코드 (수학적 접근)

// 직접 위치 계산
let actualCol = direction === 1 ? currentCol : w - 1 - currentCol;

장점:

• O(1) 시간복잡도로 위치 계산한다.
• 직관적이고 간단한 로직이다.
• 높은 가독성을 가진다.