<Lv.3> 스타 수열 (프로그래머스 : C#)

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

📕 문제 설명

부분 수열은 특정 배열에 대해 원소를 제거하거나 제거하지 않을 때 기존 원소들의 순서가 유지되는 수열들을 의미한다.

다음을 만족하는 x를 스타수열이라 정의한다.
1. x의 길이는 2 이상의 짝수 (빈 수열 허용 x)
2. x의 길이가 2n이면, n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]}의 교집합 원소 개수가 1 이상
3. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1]

• Input
  1차원 정수 배열
• Output
  모든 부분 수열 중 길이가 제일 긴 스타 수열의 길이 (스타 수열 없으면 0 반환)

풀이

먼저 개수가 많은 숫자 순서로 교집합의 기준으로 삼는다. 해당 값을 기준으로 스타 수열 조건을 확인하고 스타 수열을 만족하는 경우의 수를 세서 최종적으로 2개씩이니 * 2를 해서 반환해준다.

using System;
using System.Collections.Generic;
public class Solution {
    public int solution(int[] a) {
        int answer = -1;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        
        foreach(int num in a)
        {
            if(dict.ContainsKey(num)) dict[num] += 1;
            else dict[num] = 1;
        }
        
        foreach(int key in dict.Keys)
        {
            if(dict[key] > answer) 
            {
                int count = 0;
                int index = 0;
                
                while(index < a.Length-1)
                {
                    // 스타 수열 조건 만족 불가능한 경우
                    if(a[index] != key && a[index+1] != key || a[index] == a[index+1]) 
                    {
                        index++;
                        continue;
                    }
                    // 스타 수열 만족 (count 세기)
                    count += 1;
                    index += 2;
                }
                answer = Math.Max(answer, count);
            }
        }
        
        if(answer == -1) return 0;
        return answer * 2;
    }
}

결과