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

자바는 별로 인기가 없나보다... 근데 기업들은 자바 찾으니 

파이썬에서 자바로 갈아타고 개 후회중인데, 이미 메인 알고리즘 학습 다 이걸로 해서 뭐 갈아탈수도 없고 

화난당... 후..

그래도 계속 풀어본다... 요새 연습하는게 에디터 없이 푸는건데.. java 에디터 없이 풀기 죽을 맛이다. 그래도 이문제는 

길지 않아서 다행이다..ㅠㅜㅠㅜ 

문제설명 

문제 설명

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

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

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

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

---

입출력 예

stickeranswer

[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

입출력 예 설명

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

열심히 이문제 조합으로 풀려고 난리를 쳤다.. ㅋㅋㅋㅋㅋ 비트 마스크 연습은 제대로 되었다... 가지치기 될 수 있는 문제도 아니라 엄청 고민했는데..

아.. 맞다.. memo가 있었지.. level 4라서 메모는 아닐꺼라 생각한 내 자신이 문제가 있다.. 앞으로 적어둔다.. 

시간 초과.. level 4.. 메모.. 메모이제이션...  

메모이제이션만 활용하면 금방 풀린다. 대신 생각할 것이 원형이기 때문에, 0번 칸을 붙이는 경우랑 N-1번 칸을 붙이는 경우를 구별해서 생각해 줘야 한다는 것이다. 그리고  조건상 스티커의 값이 자연수라 가능한 해결책이기도 하다.

Java 코드 

class Solution {
    public int solution(int sticker[]) {
        int answer = 0; 
        int N = sticker.length;
        if (N==1)return sticker[0];
        if(N==2) return sticker[0]>sticker[1]?sticker[0]:sticker[1];
        if(N==3){
            if(sticker[0]>=sticker[1] && sticker[0]>=sticker[2])return sticker[0];
            else if(sticker[1]>=sticker[0] && sticker[1]>=sticker[2])return sticker[1];
            else return sticker[2];
        }
        int [] memo = new int[N];
        memo[0] = sticker[0];
        memo[1] = memo[0];
        for(int i = 2; i<N-1;i++){
            memo[i] = memo[i-2]+sticker[i]>memo[i-1]?memo[i-2]+sticker[i]:memo[i-1];
        }
        answer = memo[N-2];
        memo[0] =0;
        memo[1] = sticker[1];
        for(int i = 2; i<N;i++){
            memo[i] = memo[i-2]+sticker[i]>memo[i-1]?memo[i-2]+sticker[i]:memo[i-1];
        }
       return answer>memo[N-1]?answer:memo[N-1];
    }
}

요상하게 sicker의 길이를 3까지 해 둔 이유는  풀다가 이상하게 계속 틀려서 하나 늘려봤는데, 다른 이유였다..  그냥 새로 다시 다 짜니 풀렸다.ㅠㅠㅜㅜㅠ 처음 메모 쓴 코드가 왜 틀렸는지는 아직 모른다...ㅠㅜㅠㅜ 이건 제대로 된 코드니 잘 돌아간다.