프로그래머스

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

작성자: 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개를 꺼냅니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 크게 두 가지 방식으로 나뉩니다.

  • yoonjuhan의 Python 풀이는 창고를 층별 리스트로 구성해 상자 위치를 직접 확인하는 시뮬레이션 접근을 소개합니다.
  • Queue-ri의 풀이는 목표 상자와 마지막 상자의 층·열 위치를 비교해 수식으로 답을 구하는 방식을 사용합니다.

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

마무리

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

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