프로그래머스

프로그래머스 택배 상자 꺼내기 풀이: 지그재그 위치 계산

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 택배 상자 꺼내기
  • 출처: 프로그래머스, 2025 프로그래머스 코드챌린지 2차 예선
  • 자체 판단 난이도: Level 1

1. 문제 요약

1번부터 n번까지의 택배 상자를 한 층에 w개씩 쌓는다. 첫 번째 층은 왼쪽에서 오른쪽으로, 두 번째 층은 오른쪽에서 왼쪽으로, 세 번째 층은 다시 왼쪽에서 오른쪽으로 쌓는 지그재그 방식이다.

손님이 num번 상자를 요청했을 때, 그 상자 위에 있는 상자를 먼저 모두 꺼내야 한다. num번 상자 자신을 포함해 꺼내야 하는 상자의 총개수를 구한다.

핵심은 실제 창고를 배열로 만들 필요 없이 다음 두 가지를 계산하는 것이다.

  • num번 상자가 위치한 층과 열
  • 가장 위층에 같은 열의 상자가 존재하는지 여부

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

수식 도출

상자 번호는 w개 단위로 한 층을 구성한다. 0부터 시작하는 층 번호는 다음과 같이 구할 수 있다.

row = (num - 1) // w

num - 1을 사용하는 이유는 상자 번호는 1부터 시작하지만 나머지 연산과 몫 계산은 0부터 시작하면 편하기 때문이다.

지그재그 열 계산

짝수 층은 왼쪽에서 오른쪽으로 놓이고, 홀수 층은 오른쪽에서 왼쪽으로 놓인다. 물리적인 왼쪽 열을 기준으로 계산하면 다음과 같다.

offset = (num - 1) % w

if row % 2 == 0:
    col = offset
else:
    col = w - 1 - offset

위에 있는 상자 수 계산

가장 위층 번호는 (n - 1) // w다. 위층에 상자가 하나라도 있다면 num번 상자부터 그 위층까지의 층 수를 기본값으로 잡을 수 있다.

마지막 층이 w개로 꽉 차지 않았다면 같은 열에 상자가 없을 수 있다. 마지막 층의 실제 상자 수는 다음과 같다.

top_count = n % w
if top_count == 0:
    top_count = w

마지막 층이 짝수 층이면 왼쪽 열부터 top_count개가 채워지고, 홀수 층이면 오른쪽 열부터 top_count개가 채워진다. col이 이 범위에 포함될 때만 마지막 층의 상자를 하나 더 꺼내야 한다.

복잡도

상자의 층과 열을 계산하는 산술 연산만 수행하므로 시간 복잡도는 O(1), 추가 공간 복잡도도 O(1)이다.

마지막 층이 답을 바꾸는 조건

상자 전체를 만들 필요 없이 목표 상자의 층과 물리적 열만 구하면 된다. 위층 상자가 같은 열에 있는지는 마지막 층이 어느 방향에서 몇 칸 채워졌는지만으로 결정되므로, 마지막 층 하나만 별도로 확인한다.

오답 접근과 반례

층 번호만 같거나 다르다는 정보로는 꺼낼 개수를 정할 수 없다. n = 22, w = 6, num = 8에서는 마지막 층이 4개만 채워져 있지만 목표 열과 겹치므로 위층 상자도 포함해야 한다. 마지막 층의 방향과 실제 길이를 함께 봐야 한다.

3. 문제 해결 코드 (Python)

def solution(n, w, num):
    target_row = (num - 1) // w
    offset = (num - 1) % w

    # 층마다 상자를 놓는 방향이 바뀝니다.
    if target_row % 2 == 0:
        target_col = offset
    else:
        target_col = w - 1 - offset

    top_row = (n - 1) // w
    top_count = n % w or w

    answer = top_row - target_row + 1

    # 마지막 층에 target_col 위치의 상자가 없으면 하나를 제외한다.
    if top_row % 2 == 0:
        has_top_box = target_col < top_count
    else:
        has_top_box = target_col >= w - top_count

    if not has_top_box:
        answer -= 1

    return answer

예시 흐름

n = 22, w = 6, num = 8인 경우를 살펴보자.

  • 8번 상자는 0부터 세어 1번 층에 있다.
  • 두 번째 층은 오른쪽에서 왼쪽으로 쌓으므로 8번 상자의 물리적 열은 오른쪽에서 두 번째다.
  • 가장 위층은 3번 층이고, 22번 상자까지 있으므로 마지막 층에는 왼쪽부터 4개가 채워진다.
  • 8번 상자와 같은 열에 위층 상자가 있으므로 8번, 위의 상자 2개를 합쳐 총 3개를 꺼낸다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 마지막 층과 같은 열의 상자를 포함하는지 확인할 수 있다.

assert solution(22, 6, 8) == 3
assert solution(1, 1, 1) == 1

4. 참고 풀이 비교

  • Queue-ri의 풀이는 목표 상자와 마지막 상자의 층·열 위치를 비교해 수식으로 답을 구하는 방식을 사용한다.

시뮬레이션 방식은 구조를 눈으로 확인하기 쉽다는 장점이 있다. 하지만 n과 w가 주어졌을 때 필요한 위치 정보가 규칙적으로 계산되므로, 이 글에서는 배열을 만들지 않고 O(1) 산술 계산만 사용하는 방식을 선택했다.

마무리

지그재그로 쌓인 상자를 다루는 문제에서는 상자 번호를 층과 열로 바꾸는 과정이 핵심이다. 층의 홀짝으로 방향을 구분하고, 마지막 층의 실제 길이만 따로 처리하면 전체 창고를 직접 구현하지 않아도 답을 구할 수 있다.

#수학#프로그래머스#난이도 1