[프로그래머스] 택배 상자 꺼내기

[문제]

1 ~ n의 번호가 있는 택배 상자가 창고에 있습니다. 당신은 택배 상자들을 다음과 같이 정리했습니다.

 

왼쪽에서 오른쪽으로 가면서 1번 상자부터 번호 순서대로 택배 상자를 한 개씩 놓습니다. 가로로 택배 상자를 w개 놓았다면 이번에는 오른쪽에서 왼쪽으로 가면서 그 위층에 택배 상자를 한 개씩 놓습니다. 그 층에 상자를 w개 놓아 가장 왼쪽으로 돌아왔다면 또다시 왼쪽에서 오른쪽으로 가면서 그 위층에 상자를 놓습니다. 이러한 방식으로 n개의 택배 상자를 모두 놓을 때까지 한 층에 w개씩 상자를 쌓습니다.

위 그림은 w = 6일 때 택배 상자 22개를 쌓은 예시입니다.

다음 날 손님은 자신의 택배를 찾으러 창고에 왔습니다. 당신은 손님이 자신의 택배 상자 번호를 말하면 해당 택배 상자를 꺼내줍니다. 택배 상자 A를 꺼내려면 먼저 A 위에 있는 다른 모든 상자를 꺼내야 A를 꺼낼 수 있습니다. 예를 들어, 위 그림에서 8번 상자를 꺼내려면 먼저 20번, 17번 상자를 꺼내야 합니다.

 

당신은 꺼내려는 상자 번호가 주어졌을 때, 꺼내려는 상자를 포함해 총 몇 개의 택배 상자를 꺼내야 하는지 알고 싶습니다.

 

창고에 있는 택배 상자의 개수를 나타내는 정수 n, 가로로 놓는 상자의 개수를 나타내는 정수 w와 꺼내려는 택배 상자의 번호를 나타내는 정수 num이 매개변수로 주어집니다. 이때, 꺼내야 하는 상자의 총개수를 return 하도록 solution 함수를 완성해 주세요.

 

[제한사항]

2 ≤ n ≤ 100

1 ≤ w ≤ 10

1 ≤ num ≤ n

 

[풀이]

def solution(n, w, num):
    boxes = []

    number = 1

    while number <= n:
        row = []

        for _ in range(w):
            if number <= n:
                row.append(number)
                number += 1

        if len(boxes) % 2 == 1:
            row.reverse()

        boxes.append(row)

    target_col = 0

    for i in range(len(boxes)):
        for j in range(len(boxes[i])):
            if boxes[i][j] == num:
                target_col = j

    answer = 0

    for i in range(len(boxes)):
        if target_col < len(boxes[i]) and boxes[i][target_col] >= num:
            answer += 1

    return answer

이 문제는 상자가 지그재그로 쌓인다는 점을 먼저 이해해야 한다.

상자는 한 층에 w개씩 놓이고, 첫 번째 층은 왼쪽에서 오른쪽으로, 두 번째 층은 오른쪽에서 왼쪽으로 상자를 놓는다.

층이 올라갈 때마다 방향이 반대로 바뀐다. 따라서 2차원 배열을 만들어 상자를 실제로 쌓인 모양처럼 저장하는 방식으로 풀 수 있다.

예를 들어 n = 22, w = 6이라면 상자는 다음과 같이 저장된다.

[
[1, 2, 3, 4, 5, 6],
[12, 11, 10, 9, 8, 7],
[13, 14, 15, 16, 17, 18],
[22, 21, 20, 19]
]

첫 번째 줄은 왼쪽에서 오른쪽으로 1부터 6까지 저장된다.

두 번째 줄은 원래 7부터 12까지 만들어진 뒤, 방향이 반대이므로 reverse를 사용해 [12, 11, 10, 9, 8, 7] 형태로 저장한다.

 

그 다음에는 꺼내려는 상자 num이 몇 번째 열에 있는지 찾아야 한다.

상자를 꺼내려면 해당 상자 위에 있는 상자들을 먼저 꺼내야 한다.

예를 들어 num = 8이라면 8은 두 번째 층의 5번째 열에 있다.

같은 열의 위쪽에는 17번, 20번 상자가 있다.

따라서 17번과 20번을 먼저 꺼낸 뒤, 8번 상자를 꺼내야 하므로 총 3개의 상자를 꺼내야 한다.

배열에서 아래층부터 위층 순서로 저장했기 때문에, 같은 열에 있는 상자 중 num 이상인 값들을 세면 된다.

상자 번호는 위로 갈수록 커지기 때문에, 같은 열에서 num보다 큰 번호는 num 위에 있는 상자라고 볼 수 있다.

단, 마지막 층은 w개가 꽉 차지 않을 수 있다.

따라서 같은 열을 확인할 때 target_col이 해당 층의 길이보다 작은지 확인해야 한다.

만약 target_col이 해당 층의 길이보다 크거나 같으면, 그 층에는 해당 열의 상자가 없는 것이므로 검사하지 않는다.

최종적으로 같은 열에서 num보다 크거나 같은 상자의 개수를 세면, 꺼내야 하는 상자의 총 개수가 된다.

num 자기 자신도 꺼내야 하므로 num과 같은 경우도 포함한다.

 

[시간복잡도]

모든 상자를 한 번씩 방문하므로 O(n)