프로그래머스 - 숫자 게임 (SortedDictionary + SortedSet)

프로그래머스

 

 

이번 문제는 최소한의 차이로 반대편의 숫자보다 큰 값을 많이 제시해야하는 문제이다.

 

예시로 [5,1,3,7] 이 있다면 [2,2,6,8] 의 패를 가지고 효율적으로 최대한 많이 이기려면

1에 2로 승리

3에 2로 패배

5에 6으로 승리

7에 8로 승리

의 방식이 존재한다

 

이떄 각 원소의 값과 길이가 상당이 크기 때문에 시간 누적도를 신경쓰며 풀어야 하는 문제이다.

 

 

 

 

---

 

 

 

 

처음에는 dictionary를 써서 아래와 같이 풀어보았다

 

public int solution(int[] A, int[] B)
{
    int answer = 0;
    Dictionary<int, int> dictA = new Dictionary<int, int>();
    for(int i = 0; i < B.Length; i++)
    {
        if (dictA.ContainsKey(B[i]))
            dictA[B[i]]++;
        else
            dictA.Add(B[i], 1);
    }
    for (int i = 0; i < A.Length; i++)
    {
        if (dictA.Count == 0) break;

        var key = dictA.Keys.FirstOrDefault(k => k > A[i]);

        if (key == 0) dictA.Remove(dictA.Keys.First()); // A[i]보다 큰 값이 없으면 가장 작은 값 대입
        else
        {
            answer++;
            if (dictA[key] == 1)
                dictA.Remove(key);
            else
                dictA[key]--;
        }
    }
    return answer;
}

 

 

시간 누적도를 어느정도 생각해서 dictionary를 사용하여 낮은 값을 등록하고,
key로 관리한다면 효율적이지 않을까 라고 생각했지만

 

 

시간 초과가 떳고, 더 효율적인 구조가 필요했다.

 

 

---

 

 

 

때문에 과거 잠깐 학습한 적이 있는 처음부터 오름차순으로 배열되어 있고, min(), max() 등의 연산에서 좋은 효율을 보이는

SortedDictionary 를 떠올렸고, 이를 SortedSet와 함께 활용해 보았다.

 

 

 

public int solution(int[] A, int[] B)
{
    int answer = 0;
    SortedDictionary<int, int> dictA = new SortedDictionary<int, int>();
    SortedSet<int> keys = new SortedSet<int>();

    for (int i = 0; i < B.Length; i++)
    {
        if (dictA.ContainsKey(B[i]))
            dictA[B[i]]++;
        else
            dictA.Add(B[i], 1);

        keys.Add(B[i]);
    }

    for (int i = 0; i < A.Length; i++)
    {
        if (dictA.Count == 0) break;

        int key;

        // A[i]보다 큰 값 찾기
        var view = keys.GetViewBetween(A[i] + 1, int.MaxValue);
        if (view.Count > 0)
        {
            key = view.Min;
            answer++;
        }
        else
            key = keys.Min; // A[i]보다 큰 값이 없으면 가장 작은 값 대입

        if (dictA[key] == 1)
        {
            dictA.Remove(key);
            keys.Remove(key);
        }
        else
            dictA[key]--;
    }
    return answer;
}