[프로그래머스] Lv.1 택배 상자 꺼내기 (Java)

요즘 백엔드 직군 코딩 테스트를 Java로만 제한하는 트렌드로 변하기 시작했다.

그래~ 개발도 그렇고, 과제 테스트도 그렇고, 이제 Java도 C처럼 편하게 다루려면 풀긴 해야지

 

그래서 오늘부터 Java로 첫 ps 도전~

 

 

문제 내용

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

 

 

 

풀이

상하차의 고충

 

그냥 원하는 택배 위에 놓인 애들 다 꺼내야 하는 문제다.

 

뭐, 그냥 배열에 순서대로 넣고 인덱스 올리면서 슥슥 더하면 되는 거 아니냐?

...고 할 수 있지만 나는 효율적인 게 좋다.

 

그런 흔한 풀이가 싫어~ 난 다르게 풀 거야

 

 

레벨 1? Java의 한계? 그런 거 필요없고 아주 효율적으로 풀어주지

제한이 몇이든 빠르게 풀리도록 만들 거다.

규칙을 찾아보자

 

 

 

규칙 1: 반복되는 덧셈값 찾기

 

먼저 w 만큼의 간격으로 줄이 바뀌는데 ㄹ 모양으로 꼬아서 배치했기 때문에 각 층마다 차가 다르다.

하지만 달라지는 값이 일정하다. 

그리고 그 값은 같은 열에서 층을 올라가면서 계속 반복된다.

11 -> 1 -> 11 -> 1 또는 7 -> 5 -> 7...

 

반복되는 규칙적인 값들은? 이용할 수 있다~

 

 

규칙 2: num이 속한 층(level) 구하기

각 층을 짝수층, 홀수층으로 두자.

층은 level이라고 부를 거고 이 레벨은 어떻게 구할 수 있을까?

각 층은 w개 만큼 채워진 후 올라가니, w 가지고 어떻게 해볼 수 있을 거라는 감이 올 거다.

지금은 w가 6이니, 이해하기 쉽도록 6으로 예를 들어볼게.

 

제일 아랫층인 짝수층은 1 ~ 6으로 이뤄져있고, 각각을 6으로 나누면 0.x ~ 1.0이 나온다.

바로 위 층인 홀수층은 7 ~ 12로 이뤄져있고 각각을 6으로 나누면 1.x ~ 2.0이 나온다.

규칙이 보이나? 6으로 나눠떨어지면 소수점이 0으로 끝나고,

그렇지 않으면 소수점이 붙는다.

 

 

모듈러 연산(%)으로 나눠떨어지면 -1을 해주고, 아닌 경우는 소수점을 버린다(정수화)

그럼 결과는 아래부터 0, 1, 2, 3 ...이 나오게 된다.

결과적으로 이 값들을 2로 모듈러 연산하면 짝, 홀, 짝, 홀로 나눌 수 있게 된다.

 

 

그럼 현재 층이 짝수 층인지 홀수 층인지 알 수 있게 된다.

int level = num / w;

 

소수점이 0이라 앞의 정수부가 1올라간 w의 배수는? -1을 해주자,

// 나눠떨어지는 값은 -1 처리해야 층이 같아짐.
        if (num % w == 0) level--;

 

 

그리고 지금 층이 짝수 층인지, 홀수 층인지 알 수 있게 저장해두자.

2로 모듈러 연산한 값을 저장해두자. 나중에 쓸 거다.

int ori_level = level % 2;

 

 

규칙 3: 층 사이 차이값 패턴 찾기 ★

 

차이값 패턴 찾는 게 문제 풀이에서 가장 중요한 부분인데,

솔직히 이건 그냥 처음에 직관으로 바로 보인 거라 감이 안 잡혀도 일단 들어봐봐.

 

어쨌든 윗층과 아랫층의 차잇값도 결국 구성하는 패턴이 있을 거란 말이지.

 

 

num을 1이라 가정하고 1과 12를 볼까?

12와 1의 차이는 11.

1은 6에서 5부족하고, 12는 다음 계층의 7 ~ 12 중에서 부족함이 없는 애다.

부족함이 없다는 건 == 12가 6(w)으로 나눠 떨어지는 배수라는 의미다.

 

 

이건 참 설명하기가 쉽지 않은데,

현시점(num: 1)인 짝수층에 있는 애들은 w값인 6을 기준으로 부족한 애들이고.

다음층(12)인 홀수층에 있는 애들은 w값인 6을 기준으로 넘치는 애들이잖아?

 

그래서 짝수층은 구성값이 0 ~ 5 사이가 되고, 홀수층은 6 ~ 1 사이가 된다.

 

 

"어이, 뇌피셜 그만하고 그래서 이거 어떻게 구할 거냐?"

진정하고, 조금만 더 들어보면 이해가 갈 것이다.

 

 

원래 이 택배들은 이상적인 순서대로 쌓였다면 바로 위층의 값이 6만큼 커졌을 것이다.

그런데 ㄹ자로 꺾여서 쌓이다 보니, 차이가 짝수층, 홀수층마다 갈리게 되었다.

 

그래서 바로 위의 값이 6만큼 큰 값이 아니라, 층에 따라 11이 크든 1이 크든 들쑥날쑥 돼버렸다.

 

1과 12는 솔직히 가장 최하단층이었고, 나눠 떨어지는 가장자리 라인이었으니 다른 녀석을 예로 들어보자.

num을 8로 잡아 위의 값과의 차이를 한번 살펴보자.

 

참고로 이런 애들 패턴 찾는 건 w 같이 고정된 기준을 이용하는 게 좋다.

w로 모듈러 연산했을 때 나눠 떨어지는 애들을 기준으로 잡아보자.

 

 

어~? 이거 보이죠?

어라? 지금 층의 보스인 12랑 나는 4만큼 차이나는데,

내 바로 위에 사는 17도 결국 4만큼 차이나는 위치에 있겠네?

그럼 나(8)로부터 4 + 4 + 1 위치에 있다는 거구나?

 

 

그러면 이 차잇값을 구하는 공식을 알 수 있겠구나~

(num + (w - 1)) - ((num + (w - 1)) % w)

 

"아니, 근데 8한테만 되는 거 아님?"

오케이, 다른 애들에게도 대입해서 일치하나 확인해보자.

 

 

num을 3으로 잡는다면, 층도 짝수층이고 8이랑 위치도 다르다.

그런데 이 구조를 딱 보면 알겠지만 솔직히 다를 수가 있겠냐

3은 지금층 보스인 6이랑 3만큼 차이나고,

바로 위에 사는 10도 3만큼 떨어진 내 바로 위에 있겠구나~가 보이잖아?

 

그럼 차이값 패턴은 맞다고 볼 수 있고,

이 차이값을 가지고 바로 위의 값을 알아내는 게 우리의 목표잖아.

그럼 3 바로 위에 있는 10도 어떻게 구하겠어?

10 <= 현재 값 3에서 (3 + 3 + 1) 더하면 나오겠지?

 

이걸 공식화 하면 

// 계층별 덧셈 규칙값.
        int tmp = (num + (w - 1)) - ((num + (w - 1)) % w);
        int gap = (tmp - num) * 2 + 1;

이렇게 구할 수 있다는 거 이해하겠어?

 

 

 

그리고 각 층마다 달라지는 차이값의 합은 결국 층을 나누는 기준인 w의 2배가 된다는 걸 이해하겠어?

지금 w는 6이었고, ㄹ자로 꼬여서 올라가는 특성상 2계층 간의 차이값을 더하면 w의 2배인 12가 만들어지게 돼.

 

그럼 이렇게 구한 공식을 num에서부터 각 차이값들을 층마다 갈아끼워주면서 올라가면 구할 수 있다는 거야.

 

 

 

마무리: 반복문으로 num에서 n까지 홀짝 차이값 더하기

for (; num <= n; level++, answer++){
            if (level % 2 == ori_level) num += gap;
            else num += (w * 2) - gap;
        }

 

이제 원래 num이 있던 층에서 위로 올라가면서, 층 바뀔 때마다 해당하는 층의 차잇값 더해주면?

num이랑 그 위에 쌓인 택배 수 구하기 완료~

 

참 쉽죠?

 

글쓰다가 이것보다 더 효율적으로 푸는 방법이 떠올랐는데,

이 더하는 과정도 버리고, num에서 2계층 간의 차이가 2*w라는 점을 이용해

num부터 가장 위 지점을 2*w로 나눈 개수만큼 2*w씩 곱해서 더해주고,

 

n으로 num의 끝지점이 어떤 수에서 끝나는지 파악한 뒤에 짝수 층인지 홀수 층인지 구하고

그 층의 차잇값에 해당하는 값만큼 더해주면 반복문 따위 필요없이 바로 구할 수 있다.

 

num의 가장 위 지점을 구하는 방법은

1. 우선 n이 짝수 층, 홀수 층 중에서 어디에 속하는지 파악하고

2. n을 2*w로 모듈러 연산하면 나오는 값의 위에 n이 존재한다는 걸 알 수 있다.

3. num이 속한 층과 n이 속한 층이 같으면 같은 열, 다르면 다른 방향

4. num과 n을 2*w 모듈러 했을 때 나오는 값의 관계를 찾는다

문제처럼 n이 22, num이 8, w가 6이라면,
22 % 12 => 10
10과 8은 같은 층에다 2만큼 차이나고,
8도 짝수층, 22도 짝수층이니 같은 방향일테고, 
22에서 2만큼 차이나면 20일테니
8의 가장 위 지점은 20이다.

5. 가장 끝지점인 20과 num인 8 사이는 2*w인 12 차이만큼 나네?

8을 포함해서 1을 더해주면 바로 answer인 3이 나오죠?

 

훨씬 간단하고 효율적이죠?

당연하고 흔한 풀이가 아닌 내 풀이를 자랑하고 싶었다 후후

 

 

 

풀면서 내가 끄적였던 노트

 

만약 이거 보고 이해되면 참고

 

 

 

코드

// 자바 ps 첫 시작.
// 단순하지 않게 풀 거임.
// 이 문제는 사실 배열에 넣으면 그냥 끝이긴 하나,
// 범위가 매우 커지더라도 메모리 & 시간 걱정 제로.
class Solution {
    public int solution(int n, int w, int num) {
        int answer = 0;

        // 몇 계층(0.x~1.0)이냐 (계층에 따라 덧셈 규칙이 나뉨)
        // 홀 짝 결과로 뽑을 것 (짝홀짝홀)
        int level = num / w;

        // 나눠떨어지는 값은 -1 처리해야 층이 같아짐.
        if (num % w == 0) level--;

        int ori_level = level % 2;

        // 계층별 덧셈 규칙값.
        int tmp = (num + (w - 1)) - ((num + (w - 1)) % w);
        int gap = (tmp - num) * 2 + 1;

        // 최종 계산.
        for (; num <= n; level++, answer++){
            if (level % 2 == ori_level) num += gap;
            else num += (w * 2) - gap;
        }

        return answer;
    }
}

 

 

 

결과

 

 

이해 안 되면 댓글 고고