[프로그래머스] 쿠키 구입 / Java

문제주소 :programmers.co.kr/learn/courses/30/lessons/49995

코딩테스트 연습 - 쿠키 구입

---

<문제 설명>

문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

---

입출력 예

cookie                                                                 result

[1,1,2,3]	3
[1,2,4,5]	0

입출력 예 설명

입출력 예 #1

첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.

입출력 예 #2

주어진 조건에 맞게 과자를 살 방법이 없습니다.

 

<풀이법>

▒ 한줄 개념: memoization, 투 포인터 알고리즘 ▒ 

[2020년도 카카오 인턴십 코딩테스트] 보석 쇼핑 문제와 비슷한 느낌의 투 포인터 알고리즘을 사용하는 문제이다.

보석 쇼핑은 Lv3의 문제로 먼저 풀어보는 것도 좋을 것 같다.

programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

처음에는 반복문에서 i를 기준으로 한칸씩 줄여나가며 right값들을 탐색하는 방식으로 진행했다. 그럼 모든 i에 대해서 i^2만큼의 시간이 소요되므로 너무 많은 시간이 사용된다. 그에 따라 효율성 테스트를 통과하지 못했고, 좀 더 효율적으로 탐색할 수 있는 방식을 고민해보았다.

 

핵심 개념은 memoziation과 투 포인터 알고리즘으로, 간단한 구현 방식은 다음과 같다.

 

1. 정방향으로 더해나가는 forward[] 배열과, 역방향으로 더해나가는 backward[] 배열을 만든다.

2. 반복문을 통해 모든 인덱스 i에 대하여, 투 포인터 알고리즘을 사용한다.

    2-a. answer 보다 큰 leftValue가 나올 때까지 toLeft

    2-b. answer 보다 큰 rightValue가 나올 때까지 toRight

    2-c. 반복문을 통해 leftValue와 rightValue를 비교하고 하나하나 증가시키면서 두 값이 같을 경우 answer 값 갱신

 

---

 

1. 정방향으로 더해나가는 forward[] 배열과, 역방향으로 더해나가는 backward[] 배열을 만든다.

위와 같이 original 배열에 대해서, backward[], forward[]를 만든다. 반복문을 사용해서 배열을 생성하며, 앞에서 혹은 뒤에서부터 값을 쌓아나가며 구현하기 때문에 memoization이 사용되었다. 이렇게 하는 이유는, 만약 모든 i에 대해 처음부터 연산을 해나갈 경우 연산량이 지나치게 많아진다. 따라서 이처럼 미리 연산을 진행해 놓고, 최소한의 추가 계산만 진행한다.

 

2. 반복문을 통해 모든 인덱스 i에 대하여, 투 포인터 알고리즘을 사용한다.

 

위의 memoization(forward[] / backward[])를 사용하여, 반복문을 돌며 탐색을 진행한다. 해당 i를 left의 시작(toLeft)으로, i+1을 right의 시작(toRight)으로 하여, 양쪽 끝까지의 범위가 left와 right의 탐색 범위이다. 여기서 투 포인터 알고리즘을 사용하게 되는데, 각 left과 right는 bias값(leftBias, rightBias)을 가지고 있다. 이 bias는 현재 위치 이전까지의 값을 빼주는 역할을 한다. 위의 그림에서 보면 left 탐색 범위에서는 leftBias인 18을 빼주었고, right 탐색 범위에서는 rightBias인 7을 빼 주었다.

 

i = 3 이므로, toLeft = 3, toRight = 4이다. toLeft의 값과 toRight의 값을 비교해가는데, 조건문은 다음과 같이 3가지이다. (leftValue = toLeft의 값 / rightValue = toRight의 값)

1. leftValue == rightValue : answer 값 갱신

2. leftValue < rightValue : toLeft 한칸 이동 (toLeft--)

3. leftValue > rightValue : toRight 한칸 이동 (toRight++)

3가지 조건문을 if-else로 구현하여, toLeft와 toRight가 전체 배열 범위를 벗어나기 전까지 계속 진행한다. 이렇게 하면, 총 전체 포인터의 연산횟수(배열탐색횟수) 는 배열의 길이와 같아서 O(n)의 탐색시간만 소요된다(왼쪽으로 4칸, 오른쪽으로 5칸 = 전체 배열길이 9칸). 따라서 매번 새로 연산하면서 진행하는 것보다 훨씬 빠른 속도를 낼 수 있고, 효율성 테스트를 통과할 수 있게 된다.

이와 같은 투 포인터 탐색을 [ 0 < i < n(쿠키의 길이) ] 범위에서 모두 진행한다. 위의 간단한 구현 방식에서 2-a와 2-b는 선택사항인데, 어차피 answer보다 작은 값은 비교할 필요가 없다고 생각이 들어서 추가해주었다.

 

<코드(Java)>

class Solution {
    public int solution(int[] cookie) {
        int[] forward = new int[cookie.length];
        int[] backward = new int[cookie.length];
        int answer = 0;
        int l = cookie.length;
        
        if(cookie.length == 1)
            return answer;
        
        forward[0] = cookie[0];
        backward[l-1] = cookie[l-1];
        for(int i = 1; i < cookie.length; i++){
            forward[i] = forward[i-1] + cookie[i];
            backward[l-1-i] = backward[l-1 - i+1] + cookie[l-1-i];
        }
        
        int toLeft, toRight, leftBias, rightBias;
        for(int i = 0; i < l-1; i++){
            toLeft = i;
            toRight = i+1;
            leftBias = backward[i+1];
            rightBias = forward[i];
            
            while(toRight < l && forward[toRight]-rightBias < answer)
                toRight++;
            
            while(toLeft > -1 && backward[toLeft]-leftBias < answer)
                toLeft--;
            
            while(toLeft > -1 && toRight < l){
                int leftValue = backward[toLeft]-leftBias;
                int rightValue = forward[toRight]-rightBias;
                if(leftValue == rightValue){
                    answer = leftValue;
                    toRight++;
                    toLeft--;
                }else if(leftValue < rightValue)
                    toLeft--;
                else
                    toRight++;
            }
        }
        
        return answer;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest