[프로그래머스 C#] Lv.3 스타 수열

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

어떤 수열의 부분 수열들에 대해 조건을 만족하는 스타수열의 최대 길이를 구하는 문제

 

스타 수열이 되기 위한 조건

- 2개씩 순서대로 짝을 지어 구성된 모든 집합에 하나의 수가 교집합으로 존재해야 함

 -> 길이가 2인 부분집합의 개수 x 2 = 스타 수열의 길이

 

풀이 순서

1.배열 a에 있는 모든 정수를 구함2. 모든 정수 하나하나에 대하여 스타 수열이 되는 최대 길이를 구함3. 2번 에서 구한 값 중 최대 길이를 구하여 리턴

 

핵심 포인트

- 연산 최적화를 위해 배열 a에 있는 어떤 정수의 개수가 이미 구했던 스타 수열의 부분 집합의 개수보다 많다면 가능한 최대 기댓값보다 이미 구한 스타 수열의 길이가 더 길기 때문에 길이를 측정할 필요가 없음- 부분 수열의 개수를 카운트 할 때, 부분 수열이 가능한 경우보다 불가능한 경우에 초점을 맞추는 것이 더 편리함

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int solution(int[] a)
        {
            int answer = 0;
            var dict = new Dictionary<int, int>(); // <정수 값, 정수 개수>

            // 배열 a안에 존재하는 모든 정수의 개수를 파악
            foreach (int num in a)
            {
                if (dict.ContainsKey(num))
                    dict[num]++;
                else
                    dict.Add(num, 1);
            }
            
            // 존재하는 모든 key를 교집합으로 두는 스타 수열 구하기 
            foreach (int key in dict.Keys)
            {
                int count = 0; // 스타수열 안에 길이가 2인 부분수열의 개수

                // 스타 수열의 길이를 파악할 필요가 없는 경우
                if (answer > dict[key])
                    continue;

                // key를 교집합으로 갖는 부분 수열의 개수 구하기
                for (int i = 0; i < a.Length - 1; i++)
                {
                    // 부분 수열이 될 수 없는 경우
                    if (a[i] != key && a[i + 1] != key)
                        continue;
                    if (a[i] == a[i + 1])
                        continue;

                    // 부분 수열 발견
                    count++;
                    i++;
                }

                // 최대 값이라면 갱신
                if (answer < count)
                    answer = count;
            }

            // 스타 수열의 길이 = 부분 수열의 개수 * 2
            return answer * 2;
        }
    }