코딩 테스트 준비 - 택배 상자 꺼내기

date

Sep 1, 2025

slug

coding-test-zigzag-box-retrieval

author

status

Public

문제 링크

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

풀이 방법

지그재그(좌 → 우, 그 위층은 우 → 좌)로 한 줄에 w개씩 상자를 쌓습니다.

번호 num 상자를 꺼내려면 그 상자 위에 있는 같은 열의 상자들만 치우면 됩니다.

따라서 핵심은 num이 놓인 열 인덱스 column를 구하고, 위쪽 각 행에 그 열이 존재하는지만 확인하면 됩니다.

1) `num`의 (행, 열) 구하기 (0-기준)

row = (num - 1) // w : num의 행(아래에서 0번째)

position = (num - 1) % w : 그 행에서의 위치(0…w-1)

행의 진행 방향에 따라 열이 달라집니다.

짝수 행(아래서 0,2,4… ⇒ 좌 → 우): column = position
홀수 행(1,3,5… ⇒ 우 → 좌): column = w - 1 - position

2) 맨 위 행(부분 행 가능) 정보

맨 위 행 index: top = (n - 1) // w

맨 위 행에 실제로 채워진 칸 수: topColumn = n % w

topColumn == 0이면 맨 위 행도 꽉 찼음
topColumn > 0이면 맨 위 행은 부분 행

부분 행에서 “존재하는 열”의 범위는 채운 방향에 따라 다릅니다.

top이 짝수 행(좌 → 우)이면 존재 열: 0 … t-1 → 조건: column < topColumn

top이 홀수 행(우 → 좌)이면 존재 열: w-t … w-1 → 조건: column >= w - topColumn

topColumn == 0이면 모든 열 존재

3) 정답

num이 있는 행부터 맨 위 행까지 올라가며, 그 열이 존재하는 행 수를 세면 됩니다.

수식으로는:


answer = (top - r) + (맨 위 행에 열 c가 존재 ? 1 : 0)

(top - r) : num 위에 있는 가득 찬 행의 수

+ 1 : 맨 위 행이 존재하고 그 행에 열 c가 있을 때만

시간 복잡도 / 공간 복잡도 / 엣지 케이스

시간 복잡도: O(1)

공간 복잡도: O(1)

엣지 케이스

n <= w (한 행만 존재): 항상 1
n % w == 0 (맨 위도 꽉 참): 맨 위 행은 무조건 열 c가 존재

풀이 코드 (JavaScript)


function solution(n, w, num) {
  const row = Math.floor((num - 1) / w);
  const position = (num - 1) % w;
  const column = (row % 2 === 0) ? position : (w - 1 - position);
    
  const top = Math.floor((n - 1) / w);
  const topColumn = n % w;
    
  let topHasColumn;
  if (topColumn === 0) topHasColumn = true;
  else if (top % 2 === 0) topHasColumn = (column < topColumn);
  else topHasColumn = (column >= w - topColumn);
    
  return (top - row) + (topHasColumn ? 1 : 0);
}