택배 상자 꺼내기

문제

1부터 N번까지의 번호가 적힌 택배 상자를 창고에 정리합니다. 가로로 W개씩 상자를 놓되, 한 층이 채워지면 방향을 바꾸어 지그재그(스네이크) 형태로 위층에 상자를 계속 쌓습니다. 손님이 특정 번호(num)의 택배 상자를 찾으러 왔을 때, 해당 상자를 꺼내기 위해 그 위에 쌓인 상자들까지 포함하여 총 몇 개의 상자를 꺼내야 하는지 구하는 프로그램을 작성하는 문제입니다.

• 입력: 창고에 있는 택배 상자의 총 개수 n (2 ≤ n ≤ 100), 가로로 놓는 상자의 개수 w (1 ≤ w ≤ 10), 꺼내려는 택배 상자의 번호 num (1 ≤ num ≤ n)
• 출력: 꺼내야 하는 상자의 총 개수를 반환합니다.

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

풀이: 2차원 배열을 활용한 지그재그 시뮬레이션

상자가 지그재그로 쌓이는 규칙을 2차원 배열로 직접 시뮬레이션하여 목표 상자의 위치를 찾고, 그 위에 쌓인 상자들의 개수를 세는 직관적인 풀이입니다.

• 창고 배열 선언: 최대 상자의 개수가 100개이고 가로 길이가 W이므로, 상자가 아무리 높이 쌓여도 세로(층)는 100을 넘지 않습니다. 따라서 100 x W 크기의 2차원 배열 a를 선언하여 창고를 모사합니다.
• 지그재그 배치 (방향 전환): d 변수를 두어 1이면 오른쪽으로 이동(x++), -1이면 왼쪽으로 이동(x--)하게 합니다.
  • 이동하려는 다음 위치가 가로 범위를 벗어날 경우(왼쪽 끝 x == 0에서 왼쪽 이동, 또는 오른쪽 끝 x == w - 1에서 오른쪽 이동), 방향을 반대로 뒤집고(d *= -1) 층을 한 칸 위로 올립니다(y++).
• 목표 상자 위치 추적: 1번 상자부터 N번 상자까지 배치하는 과정에서, 현재 배치하는 상자의 번호 i가 목표 상자 num과 같다면 그 위치 (numY, numX)를 변수에 저장해 둡니다.
• 꺼낼 상자 개수 카운트: 배치가 모두 끝나면, 저장해둔 목표 상자의 위치 numY부터 시작하여 동일한 열(numX)을 따라 위로 올라가며 상자를 카운트합니다. a[numY][numX]의 값이 0(빈 공간)이 될 때까지 ans를 1씩 증가시키고 numY++를 수행하여 정답을 도출합니다.

코드

class Solution {
    public int solution(int n, int w, int num) {
        // n이 최대 100이므로 층수(세로)를 여유 있게 100으로 잡음
        int[][] a = new int[100][w];
        int y = 0;
        int x = 0;
        int d = 1; // 1: 오른쪽으로 이동, -1: 왼쪽으로 이동
        int numY = -1, numX = -1;
        
        // 1번부터 n번 상자까지 순서대로 배치
        for (int i = 1; i <= n; i++) {
            a[y][x] = i;
            
            // 목표 상자의 위치를 기억
            if (i == num) {
                numY = y;
                numX = x;
            }
            
            // 양 끝에 도달하면 방향을 바꾸고 층을 올림
            if ((x == 0 && d == -1) || (x == w - 1 && d == 1)) {
                d *= -1;
                y++;
                continue;
            }
            
            // 방향에 따라 x 좌표 이동
            x += d; 
        }
        
        int ans = 0;
        // 목표 상자부터 그 위에 쌓인 상자(0이 아닌 곳)의 개수를 셈
        while (true) {
            if (a[numY][numX] == 0) {
                break;
            }
            ans++;
            numY++; // 위층으로 이동
        }
        
        return ans;
    }
}

알고리즘 분류

구현 (Implementation), 시뮬레이션 (Simulation)