[프로그래머스] 스타 수열

문제 설명

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

문제 풀이

• 특정 숫자(num)를 교집합으로 하는 스타 수열의 집합 갯수는 아래처럼 구할 수 있다.

  • a 배열의 길이와 동일한 chk 배열을 준비한다.
  • a 배열을 순회하며 특정 숫자(num)를 만나면 아래 조건을 확인한다.
    - 해당 인덱스 이전 인덱스의 값이 num과 다르고 chk=false이면 : cnt 증가, 방문체크
    - (위 조건 불만족했을 경우) 해당 인덱스의 다음 인덱스에 대해 동일 검사 수행

• 문제에서 배열의 원소로 가능한 숫자는 0~50만인데 최악의 경우 위 로직을 50만 반복하면 시간초과 발생
• 위 로직을 처음 수행할때 배열을 순회하며 각 숫자의 갯수를 카운트 해줌.
• 0~50만 수에 대해 위 로직을 반복하되 현재까지의 최대값 >= 해당 숫자의 갯수이면 로직 수행X (스타 수열의 집합 수는 해당 숫자의 갯수를 넘을 수 없기 때문)

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int maxCount = 0;
        int[] numCnt = new int[a.length];
        //0~a.length-1까지 숫자 반복
        for (int num = 0; num < a.length; num++) {
            if (num > 0 && numCnt[num] <= maxCount) continue;
            boolean[] chk = new boolean[a.length];
            int cnt = 0;
            for (int i = 0; i < a.length; i++) {
                if (num == 0) numCnt[a[i]]++;
                if (a[i] != num) continue;
                //1. 해당 숫자 이전 숫자가 사용 가능하면
                if (i-1 >= 0 && !chk[i-1] && a[i-1] != num) {
                    chk[i-1] = true;
                    chk[i] = true;
                    cnt++;
                }
                //2. 해당 숫자 이후 숫자가 사용 가능하면
                else if (i+1 < a.length && a[i+1] != num) {
                    chk[i+1] = true;
                    chk[i] = true;
                    cnt++;
                }
            }
            maxCount = Math.max(maxCount, cnt);
        }
        return maxCount * 2;
    }
}