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

문제 설명

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

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

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

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

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

---

입출력 예

n	w	num	result
22	6	8	3
13	3	6	4

---

잘못된 접근들..ㅋ

위 예시의 경우 8번 상자를 꺼내려면 8, 17, 20번 상자를 꺼내야 한다.

상자 숫자의 차이를 보면 +3, +9, +3...의 규칙을 갖고 있다.

 

위 예시는 6번 상자를 꺼내려면 6, 7, 12, 13번 상자를 꺼내야 하고,

숫자 차이는 +1, +5, +1...의 규칙을 갖고 있다.

 

나는 1번 문제의+3, +9, +3를 2+1, 8+1, 2+1으로,

2번 문제는 +1, +5, +1도 0+1, 4+1, 0+1으로 보고 n+1을 규칙으로 가정하고 접근했는데 아무리 생각해봐도 n을 어떻게 구할지 답이 안 나왔었다.

 

그래서 상자가 쌓인 층의 홀수층/짝수층의 규칙으로 더 좁혀서 생각해 봤다.

1번 문제의 경우 홀수층 규칙인 +3은 num%2 + 1로,

짝수층 규칙인 +9는 (w-num%2)*2 + 1로 생각했는데 이건 2번 문제에 적용되지 않았음...ㅋ

 

배열을 하나하나 만들고 하나하나 세어보는 건 메모리 낭비라고 생각해서 맞는 답이더라도 적절한 답은 아닌 거 같았고, 접근법 멀르겠어서 help를 침

 

올바른 접근

ㅜㅜㅋㅋ 나는 n+1이 접근법이라 생각했는데 n*2+1이 맞는 접근법이었다. 그림을 그려보니 확실히 이해가 간다.

8을 기준으로 4칸씩 2층 + 1하면 17 나오고, 17에서 1칸씩 2층 + 1하면 20나옴...ㄱ-

여기서도 같은 규칙이 적용됨.

6을 기준으로 2칸씩 2층 + 1, 다시 7을 기준으로 0칸씩 2층 + 1...ㅋ

 

각각 변하는 빨간색과 초록색을 n이라고 두면 n*2+1 조건이 성립한다..ㅋ

n을 구하기만 하면 됨.

 

현재 위치를 cur라고 한다면, cur와 한 층에 쌓이는 박스의 갯수인 w를 활용해 n을 다음과 같이 구할 수 있다.

n = w - ((cur - 1) % w) - 1

 

n*2+1 에 위 식을 넣어서 보면...

(w - ((cur - 1) % w) - 1)*2 + 1이 되는 것임...ㄷㄷ

---

코드

class Solution {
    fun solution(n: Int, w: Int, num: Int): Int {
        var answer: Int = 0
        var temp = num
        
        while (temp <= n) {
            temp += (w - ((temp - 1) % w) - 1) * 2 + 1
            answer++
        }
        
        return answer
    }
}

 

temp를 print해보면 num번 상자는 포함이 안 되고, 범위를 벗어난 상자까지 출력이 된다.

(ex - 8, 17, 20이 아니라 17, 20, 29)

근데 짜피 num을 제외했기 때문에 범위 벗어난 상자 추가 되어서 세어도 ㄱㅊ. 그 상자를 num상자로 보면 됨

---

이게 레벨 1...?....