[Lv. 1] 389478. 택배 상자 꺼내기

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

프로그래머스

---

문제

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

 

입출력 예

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

 

입출력 예 #1

문제 예시와 같습니다. 꺼내야 하는 상자의 총개수는 8번 상자를 포함해 3개입니다.

 

입출력 예 #2

6번 상자를 꺼내려면 먼저 13, 12, 7번 상자를 꺼내야 합니다.
따라서 4를 return 합니다.

---

풀이

class Solution {
    public int solution(int n, int w, int num) {
        // 총 몇층 몇번째
        int nF = getF(w, n-1);  // 1을 뺀다.
        int nIndex = getIndex(w, nF, n-1);
        
        // 선택한 상자
        int numF = getF(w, num-1);
        int numIndex = getIndex(w, numF, num-1);
        
        // 짝수층 ->
        // 홀수층 <-
        
        int count = (nF - numF);
        if (nF % 2 == 0) {
            count += (numIndex <= nIndex) ? 1 : 0;
        } else {
            count += (numIndex >= nIndex) ? 1 : 0;
        }
        
        return count;
    }
    
    private int getF(int w, int n) {
        return n/w;
    }
    
    private int getIndex(int w, int f, int n) {
        if(f % 2 == 0){
            return n%w; 
        } else {
            return w - 1 - (n % w);
        }
    }
}

 

 

문제 정리

1번부터 n번까지 번호가 붙은 상자가 있다.

 

상자가 쌓이는 규칙

• 한 층에 w개씩
• 왼쪽 → 오른쪽
• 다음 층은 왼쪽 ← 오른쪽
• 그 다음 층은 다시 왼쪽 → 오른쪽

상자를 꺼낼 때는, 위에 있는 상자들을 모두 꺼내야 한다.

 

num번 상자를 꺼내기 위해 꺼내야 하는 상자의 수는?

 

 

입력

• n: 상자의 총 개수 int  (2 ≤ n ≤ 100)
• gifts: 한 층에 놓는 상자의 수 int  (1 ≤ w ≤ 10)
• num: 꺼내고자 하는 상자 번호 int  (1 ≤ num ≤ n)

출력

• 상자 num을 꺼내기 위해 꺼내야 하는 상자의 수 int

 

 

n번째 상자(마지막상자)와 num번째 상자의 위치(층, index) 비교

를 통해 몇개의 상자를 꺼내야 하는지 계산 할 수 있다.

• 짝수층(0, 2, ...층): 왼쪽 → 오른쪽
• 홀수층(1, 3, ... 층): 왼쪽 ← 오른쪽
• index 는 방향 상관없이 왼쪽 → 오른쪽 (0, 1, 2, ..., w-1)

 

총 개수 공식

• num의 층 수 - n의 층수: 꺼내야되는 상자의 최소 개수 (index 무시)
• 마지막 상자가 짝수층에 있는 경우 (입출력 예 1 상황)
  
  • num의 index <= n의 index : 총 개수 + 1 
• 마지막 상자가 홀수층에 있는 경우 (문제 상황)
  
  • num의 index >= n의 index : 총 개수  + 1 

 

코드 설명

3~9행, 24~34행(메서드): n번째 상자와 num 번째 상자 위치 계산

• index 를 0부터 시작하기 위해, n-1, num-1 값을 사용
• getF: 상자가 몇층에 있는지 구하기 (0층부터 시작)
• getIndex: 상자가 몇번 인덱스에 위치했는지 구하기 (0 ~ w-1 까지)

 

14~19행: 위의 총 개수 공식 적용

 

21행: 꺼낼 상자의 개수 반환

---

GitHub: https://github.com/gajicoding/coding_test/edit/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/1/389478.%E2%80%85%ED%83%9D%EB%B0%B0%E2%80%85%EC%83%81%EC%9E%90%E2%80%85%EA%BA%BC%EB%82%B4%EA%B8%B0

coding_test/프로그래머스/1/389478. 택배 상자 꺼내기 at main · gajicoding/coding_test

---

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

코딩테스트 연습 | 프로그래머스 스쿨

---