(C#) 스타 수열

https://school.programmers.co.kr/learn/courses/30/lessons/70130?language=csharp

프로그래머스

 

문제가 썩 직관적이지는 않다. 한번에 이해가 되지는 않는다.

 

스타 수열은 요컨대, 전체 수열 a를 가지고 앞에서부터 숫자를 두개씩 선택하는데, 선택된 숫자 쌍에는 항상 특정한 숫자가 포함되어야 한다는 뜻이다.

 

 처음에 생각했던 방법은, 말 그대로 앞에서부터 숫자를 두개씩 선택하고 비교하는 것이었다. 아마도 가장 무식한 방법이 아닐까싶다. 단순히 생각해도 숫자를 두개 선택하는 방법의 수 N^2, 그걸 수열의 처음부터 끝까지 반복해야하므로 또 N, 최종적으로 N^3의 시간복잡도를 가지게 된다.

 

 다음으로 생각한 방법은 전체 수열 a를 앞에서부터 훑어보면서 모든 숫자가 가질 수 있는 숫자쌍의 갯수를 세는 것이었다.

 힌트는 a의 모든 숫자는 0 이상, a의 길이 미만이라는 제한조건이었다.

 숫자의 크기가 a.Length까지로 제한되므로 모든 숫자들이 가질 수 있는 숫자쌍의 갯수를 저장하는데 길이가 a.Length인 배열만 있어도 충분하다.

 앞에서부터 인접한 숫자를 두개씩 비교하면서, 숫자가 다르면 각 숫자가 가질 수 있는 숫자쌍의 갯수 temp[i]를 증가시켰다.

 

 그러나 이 방법으로는 정확한 답을 구할 수 없었다. 같은 숫자가 인접해서 등장하는 경우, 그리고 5, 3, 5와 같이 어떤 숫자의 양쪽이 같은 숫자인 경우에 어떻게 처리해야할지가 곤란했다. 만약 더 고민해서 처리하는 방법을 고안해냈다 하더라도 이미 코드가 깔끔해 보이지는 않았다.

풀이

 마지막으로 시도한 방법은 다음과 같다.

 먼저 전체 수열 a를, 같은 숫자가 연속으로 나올때마다 자른다. 예를 들어 예제의 수열 [0, 3, 3, 0, 7, 2, 0, 2, 2, 0]의 경우, [0, 3], [3, 0, 7, 2, 0, 2], [2, 0] 세 개의 수열로 나눌 수 있다.

 그리고 각각의 부분 수열 s에서 각 숫자가 등장한 횟수와 s의 길이를 구한다.

 

 에를 들어 방금 전의 부분수열 [0, 3]은 전체 길이가 2, 각 숫자가 등장한 횟수가 [1, 0, 0, 1, ...]이 될 것이다.

 그리고 [3, 0, 7, 2, 0, 2]의 경우에는 전체 길이가 6, 각 숫자가 등장한 횟수가 [2, 0, 2, 1, 0, 0, 0, 1]이 될 것이다.

 

 부분 수열 s에서 각 숫자가 만들 수 있는 숫자쌍의 갯수는 Math.Min(num[i], s.count - num[i])이다.

 (num : 부분수열 s에서 숫자 i가 등장한 횟수, count : s의 길이)

 왜냐하면 부분수열 s에는 연속되는 숫자쌍이 절대 없기 때문이다. 모든 숫자는 인접한 다른 숫자와 쌍을 이룰 수 있다.

 만약 쌍을 이룰 다른 숫자가 부족하다면 반대로 나머지 숫자의 갯수(count - num[i]) 만큼의 쌍을 만들 수 있다.

 예를 들어 [3, 0, 3, 1, 3, 2] 이라는 부분 수열 s가 있다고 해보자. s의 길이는 6, 3의 갯수 num[3]은 3이다. 모든 3은 바로 다음 숫자와 쌍을 이룰 수 있으므로 3개의 쌍을 만들 수 있다.

 s의 마지막에 3을 하나 더 추가하면 [3, 0, 3, 1, 3, 2, 3]이 된다. 이 때 s의 길이는 7, 3의 갯수 num[3]은 4이다. 마지막으로 추가된 3은 더이상 숫자쌍을 이룰 수 없다. 이 경우 count - num[3] = 3개의 숫자쌍을 만들 수 있다.

 

 a에서 같은 숫자가 연속되는 부분을 잘랐으므로 각 부분수열 sn과 sn+1 사이에는 숫자쌍을 만들 수 없다.

 따라서 모든 부분 수열 s에서 만들 수 있는 숫자쌍의 갯수를 더하면 전체 수열 a에서 만들 수 있는 숫자쌍의 갯수와 같다.

 

 예제의 수열  [0, 3, 3, 0, 7, 2, 0, 2, 2, 0]의 경우로 예를 들어보자.

 a를 3개의 부분 수열 [0, 3], [3, 0, 7, 2, 0, 2], [2, 0]으로 나눌 수 있다. 

 첫번째 부분 수열에서 num은 [1, 0, 0, 1, 0, 0, 0, 0]이 된다.

 두번째 부분 수열에서 num은 [2, 0, 2, 1, 0, 0, 0, 1]이 된다.

 세번째 부분 수열에서 num은 [1, 0, 1, 0, 0, 0, 0 ,0]이 된다.

 각 부분 수열에서 나오는 숫자쌍의 갯수를 모두 더하면 [4, 0, 3, 2, 0, 0, 0, 1]이 된다.

 이 중 가장 큰 숫자인 4에 2를 곱해주면 최종 답 8이 나온다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] a)
    {
        int answer = -1;
        int[] counts = new int[a.Length];
        Dictionary<int, int> temp = new Dictionary<int, int>();
        int count = 0;
        for (var i = 0; i < a.Length; i++)
        {
            if (i != 0 && a[i] == a[i - 1])
            {
                foreach (var item in temp)
                {
                    counts[item.Key] += Math.Min(item.Value, count - item.Value);
                }
                count = 0;
                temp = new Dictionary<int, int>();
            }
            count++; // 부분 수열의 길이
            if (!temp.ContainsKey(a[i])) temp[a[i]] = 0;
            temp[a[i]]++; // 부분 수열에서 a[i]의 갯수
        }

        foreach (var item in temp)
        {
            counts[item.Key] += Math.Min(item.Value, count - item.Value);
        }

        for (var i = 0; i < a.Length; i++)
        {
            if (counts[i] > answer) answer = counts[i];
        }
        return 2 * answer;
    }
}

 

후기

 처음에 부분 수열에서 만들 수 있는 숫자쌍의 갯수 temp를 int[]로 만들었다가 시간 초과가 나왔다.

 temp를 int[]형으로 생성했을 때, 최악의 경우 a의 길이가 50만이고, [...3, 3, 3, 3, 3, 3...] 같은 구간이 있다고 한다면, 연속된 3마다 전체 숫자쌍의 갯수 count를 업데이트하는 작업을 수행해야 할 것이다.

 만약 전체 수열 a가 같은 숫자로만 이루어져 있다면 최종적으로 시간복잡도는 N^2가 되어 시간초과가 나온다.

 temp를 배열로 해서 부분 수열 s에서 업데이트 되지 않은 숫자들까지 계산하기 보다는, Dictionary<int, int> 형태로 해서 갱신이 있었던 숫자만 계산하는 방식으로 시간복잡도를 줄일 수 있었다.

 Dictionary는 hash 방식으로 데이터를 저장하기 때문에 반복 횟수를 획기적으로 줄여 시간적으로 크게 이득을 볼 수 있었다.