[Algorithm] Programmers :: 스타 수열

https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

int checkCount[500001] = { 0 };
int lastPos[500001] = { 0 };
 
int solution(vector<int> a)
{
    int answer = 0;
    if (a.size() == 1) return 0;
 
    memset(lastPos, -1, sizeof(lastPos));
 
    for (int i = 0; i < a.size(); ++i)
    {
        int num = a[i];
 
        if (i - lastPos[num] >= 2) // 좌측에 대한 검사
        {
            ++checkCount[num];
            answer = max(answer, checkCount[num]);
            lastPos[num] = i;
        }
        else if (i + 1 < a.size() && num != a[i + 1]) // 우측에 대한 검사.
        {
            ++checkCount[num];
            answer = max(answer, checkCount[num]);
            lastPos[num] = i+1;
        }
        else lastPos[num] = i;
    }
     
    return answer * 2;
}

 

문제를 재해석해보자면, 조건에 맞는 각 숫자의 쌍의 개수들 중 최대개수를 구하는 문제라고 설명할 수 있다.

여기서 조건이란, 특정 숫자의 조건에 맞는 쌍의 개수를 구한다고 했을 때 일단 쌍은 말 그대로 2개짜리이고 두 숫자는 같으면 안된다.(즉 특정숫자로만 이루어져 있으면 안된다. )

 

특정숫자를 0이라고 가정하고, 짝이 될 숫자가 다른 숫자이기만 하면 카운팅할건데 대신 특정숫자 0의 짝이되는 숫자는 이미 사용한것이기 때문에 다른 특정숫자0이 사용할 수는 없다.

 

이 조건에 맞춰서 각 숫자마자 쌍의 개수를 구하고 최대개수를 구하는 문제다.

 

나같은 경우 처음 풀이를 하고 제출했을 때 통과는 했는데 효율성에서 정말로 간신히 통과했다.( 2000ms도 있었던 듯)

다시 생각해서 O(N)으로 코드를 작성했더니 특정케이스에서 안되는걸 깨닫고, 다른사람 풀이를 한번 참고해서 다시 작성해봤다. 사실상 거의 코드가 동일한데, 중요한것은 해당 코드를 논리적으로 전부 이해했느냐 안했느냐이다.

 

먼저 좌측에 대한 검사를 진행한다. 좌측에 대한 검사란 바로 왼쪽 인덱스를 검사하는게 아닌 lastPos[a[i]]을 검사하는 것이다. 쌍이 맺어지기 위해선 이전의 같은숫자와의 거리가 최소 2이상벌어져있어야 맺을 수 있기 때문에 검사한다.

그리고 쌍이 맺어진거에 대해선 다른 쌍이 될 수 없다는 걸 명심해야 한다.

 

우측에 대한 검사에서는 좌측검사와 달리 우측의 숫자가 기준숫자랑 다른지 검사를 해야한다.

좌측검사는 이미 기록을 하면서 진행했기 때문에 거리체크만으로도 카운팅 할 수 있는거고, 우측검사는 아직 탐색안된부분에 대해서 검사하는 것이기 때문에 기준숫자와 다른지 검사를 해야한다.

그리고 여기서 중요한 것은, 카운팅을 한 다음 lastPos에 값을 저장할 때 i가 아닌 i+1을 검사해야 한다.

왜냐하면 말했다시피 해당숫자는 현재 i의 기준숫자가 이미 쌍으로 만들어버렸기 때문에, 현재 i이후의 인덱스의 기준숫자에서는 이 i+1의 숫자를 사용할 수 없다. 

그것에 대한 표현으로 lastPos에 i+1을 저장하는 것이다.