스티커 모으기(2)

문제 설명

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

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

 

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

 

제한 사항

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

입출력 예

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

---

문제 해설

 

스티커 때기 문제이다. 각 객체의 숫자가 매우 많기 때문에 값을 순차적으로 누적시켜가면서 계산해야 한다.

 

값이 한개가 없어졌을 때, 주변의 값또한 참조가 불가능해지는걸 생각하고 코드를 작성해야 한다.

 

전체 스티커를 계산할 때, 처음 스티커를 땔지 말지를 생각해서 누적계산하면 된다.

---

첫 번째 시도

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int sum(const vector<int>& vec) {
    int sum = 0;
    for (const int& num : vec) sum += num;
    return sum;
}

int SClamp(const int& input, const int& max)
{
    return input < 0 ? max : input > max ? 0 : input;
}

struct ValueAndRL
{
    ValueAndRL(int v, int L, int R)
        : Value(v), Left(L), Right(R)
    {};

    int Value;
    int Left;
    int Right;
};

int solution(vector<int> sticker)
{
    int answer = 0;
    while (true) 
    {
        map<int, vector<ValueAndRL>> ChackToSide;
        int Max = sticker.size() - 1;
        int All = sum(sticker);

        for (int i = 0; i <= Max; i++)
        {
            if (sticker[i] != 0) 
            {
                int Left = sticker[SClamp(i - 1, Max)];
                int Right = sticker[SClamp(i + 1, Max)];
                int Value = sticker[i];
                int key = All - (Left + Right + Value);

                ValueAndRL input(i, SClamp(i - 1, Max), SClamp(i + 1, Max));
                ChackToSide[key].push_back(input);
            }
        }

        auto it = ChackToSide.rbegin();
        if (it == ChackToSide.rend()) break;

        auto& def = it->second[0];
        answer += sticker[def.Value];
        sticker[def.Value] = 0;
        sticker[def.Left] = 0;
        sticker[def.Right] = 0;
    }
    return answer;
}

실패

 

전체 값을 한번 순회하고, 3개의 객체를 빼고 다시 순회하고 를 반복하다가 모든 값이 0이되었을 때 종료하도록 코드를 작성했다.

 

시간초과가 나타난건 당연하고, 코드가 돌아갈 때, 5, 1, 16, 17, 16  을 돌릴때, 32가 나오도록 순환해야 하는데, 그렇게 하지 못했다.

---

두 번째 시도

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int SClamp(const int& input, const int& max)
{
    return input < 0 ? max : input > max ? 0 : input;
}

int solution(vector<int> sticker)
{
    int answer = 0;
    int next = 0;
    int Size = sticker.size() - 1;

    while (next < Size) 
    {
        int find1 = 0;
        int find2 = 0;
        
        for (int i = next; i < Size; i += 2)
        {
            find1 += sticker[i];
            find2 += sticker[i + 1];
        }

        int NowMax = find1 > find2 ? next : next + 1;
        next = NowMax + 1;
        answer += sticker[NowMax];

        sticker[NowMax] = 0;
        sticker[SClamp(NowMax - 1, Size)] = 0;
        sticker[SClamp(NowMax + 1, Size)] = 0;
    }
    
    return answer;
}

실패

 

이번에는 전체 객체를 참조하되, 좀더 빠르게 동작하기 위해서 첫 값부터 순환하게 만들었다.

 

그러나, 값을 누적하지만 전 값과 전전값을 참조하지 못해 정상적인 판단이 이루어지지 못했다.

 

현재 스티커를 땔지 말지의 개념을 고민해야 하는데, 그에대한 근거가 부족했다.

 

---

세 번째 시도

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> sticker)
{
    if (sticker.size() == 1) return sticker.front();

    vector<int> DP1(sticker.size(), 0);
    DP1[0] = sticker[0];
    DP1[1] = max(sticker[0], sticker[1]);
    for (int i = 2; i < sticker.size() - 1; i++)
        DP1[i] = max(DP1[i - 1], DP1[i - 2] + sticker[i]);

    vector<int> DP2(sticker.size(), 0);
    DP2[0] = 0;
    DP2[1] = sticker[1];
    for (int i = 2; i < sticker.size(); i++)
        DP2[i] = max(DP2[i - 1], DP2[i - 2] + sticker[i]);
    return max(*max_element(DP1.begin(), DP1.end()), *max_element(DP2.begin(), DP2.end()));
}

성공

 

코드 자체를 간략화 했다.

전에 스티커를 땐 값이 더 큰지, 아니면 현재 스티커를 땐 값이 더 큰지 를 검사하고 해당 검사결과를 반영하여 현재 스티커를 땔지 여부를 확인하게 하였다.

 

그리고, 첫 값이 1인지 0인지를 기준으로 두번 검사하여, 두번검사 결과의 가장 큰 값을 결과로 도출하도록 작성했다.

 

코드가 복잡하지 않아도 결과가 나타나는걸 보아 코딩테스트 문제가 악질이다...