[70130] 스타 수열

✔ 스타 수열

[프로그래머스 70130]

문제 분석하기

교집합의 원소의 개수가 1개 이상이어야 하므로 전체 수열에서 각 인덱스에 따른 숫자의 개수를 저장한 후

각 숫자를 교집합으로 하는 스타 수열의 길이를 찾도록 함

손으로 풀어보기

1. 전체 수열에서 각 인덱스에 따른 숫자의 개수를 저장
2. 각 숫자를 교집합으로 하는 스타 수열의 길이를 찾도록 함

슈도코드 작성하기

a(1차원 정수 배열)
count(각 원소의 개수를 담은 배열)
for(num -> a만큼) {
    a 배열을 돌면서 각 원소에 따른 개수를 증가시킴
}
answer(a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 집합 개수)
for(i -> count의 길이만큼) {
    if(count[i]의 개수가 answer보다 작다면) {
        더 긴 스타 수열이 될 수 없으므로 넘어감
    }
    n(현재 스타 수열의 집합 개수)
    for(j -> a의 길이 - 1만큼) {
        if(현재 집합이 i를 포함하지 않는다면) {
            교집합의 원소의 개수가 1 이상이 될 수 없어 스타 수열이 될 부분 수열에 포함되지 않으므로 넘어감
        }
        if(집합의 두 원소가 같다면) {
            스타 수열이 될 부분 수열에 포함되지 않으므로 넘어감
        }
        두 조건을 만족한다면 스타 수열이 될 부분 수열에 포함될 수 있으므로 n 증가
        두 원소씩 살펴봐야 하므로 j 하나 더 증가
    }
    n이 answer보다 더 길다면 answer 갱신
}
answer은 집합의 개수이므로 * 2를 반환

코드 구현하기

/**
 * 70130) 스타_수열
 */
public class L042_70130 {
    // a(1차원 정수 배열)
    public int solution(int[] a) {
        // count(각 원소의 개수를 담은 배열)
        int[] count = new int[a.length];
        // a 배열을 돌면서 각 원소에 따른 개수를 증가시킴
        for (int num : a) {
            count[num]++;
        }
        // answer(a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 집합 개수)
        int answer = 0;
        for (int i = 0; i < count.length; i++) {
            // count[i]의 개수가 answer보다 작다면
            if (count[i] <= answer) {
                // 더 긴 스타 수열이 될 수 없으므로 넘어감
                continue;
            }
            // n(현재 스타 수열의 집합 개수)
            int n = 0;
            for (int j = 0; j < a.length - 1; j++) {
                // 현재 집합이 i를 포함하지 않는다면
                if (a[j] != i && a[j + 1] != i) {
                    // 교집합의 원소의 개수가 1 이상이 될 수 없어 스타 수열이 될 부분 수열에 포함되지 않으므로 넘어감
                    continue;
                }
                // 집합의 두 원소가 같다면
                if (a[j] == a[j + 1]) {
                    // 스타 수열이 될 부분 수열에 포함되지 않으므로 넘어감
                    continue;
                }
                // 두 조건을 만족한다면 스타 수열이 될 부분 수열에 포함될 수 있으므로 n 증가
                n++;
                // 두 원소씩 살펴봐야 하므로 j 하나 더 증가
                j++;
            }
            // n이 answer보다 더 길다면 이로 갱신
            answer = Math.max(answer, n);
        }
        // 스타 수열의 길이의 집합 개수 * 2를 반환
        return answer * 2;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L042_70130 solution = new L042_70130();

        int[] a = { 5, 2, 3, 3, 5, 3 };

        int result = solution.solution(a);

        System.out.println(result);
    }
}