[프로그래머스][스티커모으기(2)]

문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

나의 풀이(실패)

package programmers.lv3;

public class Sticker {

    public int solution(int sticker[]) {
        int answer = 0;

        int n = sticker.length;

        int left = 0;
        int right = 0;

        if(n == 1) return sticker[0];

        for(int lt = 0; lt < n; lt += 2){
            left += sticker[lt];

        }
        for(int rt = 1; rt < n; rt += 2){
            right += sticker[rt];
        }

        answer = Math.max(left, right);

        return answer;
    }

    public static void main(String[] args) {
        Sticker T = new Sticker();

        int[] sticker = {1, 3, 2, 5, 4};

        System.out.println(T.solution(sticker));
    }
}

• 0 ~ n 전까지 인덱스가 2씩 증가하며 더한 값 left와 1 ~ n전까지 인덱스가 2씩 증가하여 더한 값 right를 비교하여 더 큰 값을 answer에 담아주면 해결되는 문제라고 생각했다.
• 하지만 그렇지 않았다. 예외 케이스를 생각해보기엔 시간이 부족해서 다른 사람의 풀이를 봤다.(기지국 설치에서 7시간 정도의 시간을 소비했다.. 분한 마음에 포기하지 않으려 했었는데 그게 독이된 것 같다.)

다른 사람의 풀이

public static int solution(int sticker[]) {
        int answer = 0;

        int len = sticker.length;

        if (len == 1) return sticker[0];

        int[] dp1 = new int[len];
        int[] dp2 = new int[len];

        //첫번째 스티커를 떼는 방법
        dp1[0] = sticker[0];
        dp1[1] = sticker[0];
        for (int i = 2; i < len-1;i++) {
            dp1[i] = Math.max(dp1[i-1],dp1[i-2] + sticker[i]);
            System.out.println(dp1[i]);
        }

        System.out.println();

        //첫번째 스티커를 뗴지 않는 방법
        dp2[0] = 0;
        dp2[1] = sticker[1];
        for (int i = 2; i < len; i++) {
            dp2[i] = Math.max(dp2[i-1],dp2[i-2] + sticker[i]);
            System.out.println(dp2[i]);
        }

        answer = Math.max(dp1[len-2],dp2[len-1]);

        return answer;
    }

• DynamicProgramming을 이용한 풀이법이다.
• 중요한건 아직 다이나믹 프로그래밍 알고리즘을 사용할줄 모른다는 것이다.
• 다이나믹 프로그래밍은 인접한 두 수를 연속해서 더하지 않으면서, 최상의 값을 도출해내는데 유용해보인다.

후기

• 처음 내가 접근한 방식도 나쁘지 않은 방식이었다. 하지만 문제 해결에 실패하고 난 뒤에 어떤 문제가 있는걸까 고민해봤다.
• 내가 내린 결론은 수 들을 더할 때 꼭 두칸씩 뛰어가면서 더하지 않는다는 것이다. 어쩔 때는 두칸을 뛰어서 더한 값보다 세칸을 뛰어서 더한 값이 더 클 수도 있다는 사실이었다.
• 하지만 그 로직을 짜내려면 아주 오랜 시간이 걸릴 것 같았다. (사실상 문제를 알고리즘을 적용하지 않고 순수한 자바 로직으로 풀게 될 가능성이 높으니까)
• 알고리즘을 풀 때 답을 보지 않는 것이 좋다. 자신이 처한 상황에서 효율성을 고려해봐야 한다.