Programers 스티커 모으기(2)- java


문제 설명

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

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다.

단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다.

스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요.

원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

  • sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.

  • sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.

  • 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

출처 : https://programmers.co.kr/learn/courses/18/lessons/1881


풀이 과정

  1. 일반적인 경우 다이나믹 프로그래밍 기법으로 문제를 수월히 풀 수 있을 것 같았다.

  2. 일반적인 경우와 위 문제의 경우 사이의 차이점을 생각해 보니 0번째 인덱스와 마지막 인덱스가 동시에 선택 될 수 없었다.

  3. 2번을 만족 시키기 위해서 0번째 인덱스를 포기하는 경우와 마지막 인덱스를 포기하는 경우 두 가지 배열을 만들어 두 경우 중 최대값을 선택 한다.

  4. 다이나믹 프로그래밍 기법을 활용해 각 배열의 값에는 index-2, index-3 인덱스들의 값중 더 큰 값과 현재 값을 더해 저장 한다.

dp[index] = Math.max(dp[index-2], dp[index-3]);
  1. index-2의 경우는 한 칸 떨어진 스티커, index-3의 경우는 두 칸 떨어진 스티커이다. index-4는 고려하지 않아도 된다. index-2를 선택시 index-4 또한 선택 할 수 있기 때문이다.


문제 풀이 핵심

  • 입력받은 배열을 clone() 을 통해 두 가지로 나눈 뒤 하나는 0번 째 인덱스에 0을 나머지 하나는 마지막 인덱스에 0을 입력한다
        int[] dp1 =sticker.clone();     // 첫 번째 경우
        int[] dp2 =sticker.clone();     // 두 번째 경우
        
        dp1[0] = 0;
        dp2[n-1]=0;


  • 위 처럼 0번 째 또는, 마지막 인덱스에 0 을 넣으면 배열의 머리 부분과 꼬리 부분이 동시에 선택되는 경우를 막아줄 수 있다.

  • 첫 번째, 마지막 인덱스를 포기하는 각각을 선택 안하는 두 개의 경우에서 최대값을 찾아 반환하게 된다.


풀이 코드

import java.util.*;

class Solution{
    public int solution(int sticker[]){
        int answer=0;                   
        int n = sticker.length;         // 스티커 길이

        if(n<4){
            Arrays.sort(sticker);       // 길이가 3 이하라면 하나밖에 뜯지 못함
            return sticker[n-1];
        }

        int[] dp1 =sticker.clone();     // 첫 번째 경우
        int[] dp2 =sticker.clone();     // 두 번째 경우
        
        dp1[0] = 0;
        dp2[n-1]=0;

        for(int i = 2; i<n; i++){
            if(i==2){
                dp1[i] = dp1[i-2]+ dp1[i];
                dp2[i] = dp2[i-2]+ dp2[i];
                continue;
            }
            dp1[i] = Math.max(dp1[i-2], dp1[i-3]) + dp1[i];
            dp2[i] = Math.max(dp2[i-2], dp2[i-3]) + dp2[i];
        }

        Arrays.sort(dp1);
        Arrays.sort(dp2);

        return Math.max(dp1[n-1], dp2[n-1]);
    }
}


느낀 점

쉬운 난이도임에도 허덕이는 나를 보며 아직 코딩테스트를 치르기엔 많이 부족한 실력임을 느꼈다.

꾸준히 노력해야지..ㅎㅎ