[C#/프로그래머스]숫자 게임

Level3

처음에 문제보고

왜 이게 Level3이지? 그냥 정렬하고 비교해서 카운트하고 리턴하면 되지않나?

이런 안일한 생각으로 한시간 반이나 걸렸습니다. 

 

첫번째 시도

using System;

public class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Array.Sort(A);
        Array.Sort(B);
        
        int count = A.Length;
        int check=0;
        
        9 9 3 1
        10 8 2 2 
            
        1 3 9 9
        2 2 8 10
            
       
        //B의 모든수가 같을 때
        if(B[count-1]==B[0])
        {
            //B가 A의 가장 큰 수보다 클 때
            if(A[count-1]<B[0])
            {
                answer=count;
            }//작을때는 어차피 0임
           
            check=1;
        }
        else if(A[count-1]==A[0])//A의 모든 수가 같을 때
        {
            //A가 B의 가장 작은 수보다 작을 때
            if(A[0]<B[count-1])
            {
                answer=count;
            }//클때는 어차피 0임
            
            check=1;
        }
        
     
            
        if(check==0)
        {
            for(int i=0; i<count; i++)
            {
                if(B[i]>A[i]) answer++;
            }
        }
        
        
        return answer;
    }
}

 말그대로 정렬하고 많은수를 계산할 때를 대비해 가장 큰수와 작은수가 같을때 빠르게 스킵할 수 있는 조건식을 만들어서 

돌렸다. 

이 경우 테스트 코드는 통과하지만 문제가 있는데

 

1 3 9 9 

2 2 8 10 

 

이때 순서대로 비교할경우 승리 횟수는 2가 나오지만 두번째와 세번째를 바꾸면 승리 회수는 3이나온다.

단순한 그리드알고리즘으로 풀었을 경우 이런 경우의 수를 생각하지 못하고 실패한다.

두번째 시도

using System;

public class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        int check =0;
        int count = A.Length;
        
        Array.Sort(B);
        Array.Sort(A);
        
         //B의 모든수가 같을 때
        if(B[count-1]==B[0])
        {
            //B가 A의 가장 큰 수보다 클 때
            if(A[count-1]<B[0])
            {
                answer=count;
            }//작을때는 어차피 0임
           
            check=1;
        }
        else if(A[count-1]==A[0])//A의 모든 수가 같을 때
        {
            //A가 B의 가장 작은 수보다 작을 때
            if(A[0]<B[count-1])
            {
                answer=count;
            }//클때는 어차피 0임
            
            check=1;
        }
        
         int temp=0;
         if(check==0)
         {
            for(int i=0; i<count; i++)
            {
                if(B[i]>A[i])
                {
                    answer++;
                }
                else if(B[i]>=A[0])
                {
                    for(int j=0; j<i; j++)
                    {
                        if(B[i]>A[j]&&(B[j]!=A[j]))//B가 A보다 큰 경우지만 B[i]와 B[j]값이 같으면 의미없다.
                        {
                            if(B[j]>A[j]) continue;
                            temp=A[j];
                            A[j]=A[i];
                            A[i]=temp;
                            answer++;
                            
                            break;
                        }
                    }
                }
               
            }
         }
        // 1 3 3 9
        // 2 2 8 10 
        
        // 2 2 8 8
        // 1 1 8 8
        return answer;
    }
}

 그 다음 시도한 방법이  진  수를 A의 다른수와 비교해서 위치를 바꾸는 방법이였는데

당연히 이중 for문을 쓰니 시간초과가 나오고..... 하다보니 이렇게 복잡하게 하는게 정답이 아니라는 생각이 들었다. 

세번째 시도(성공)

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int[] A, int[] B)
    {
        int answer = 0;

        Array.Sort(A);
        Array.Sort(B);

        Array.Reverse(A);
        Array.Reverse(B);
        

        Queue<int> Bque = new Queue<int>(B);
     
        for (int i = 0; i < B.Length; i++)
        {
            if (Bque.Count == 0) break;
          
            if (A[i] < Bque.Peek())
            {
                answer++;
                Bque.Dequeue();
            }
        }

        return answer;
    }
}

더욱더 단순하고 빠르게 B배열을 Queue에 넣고 A와 비교해서 deque하는 방법으로 해결했다.

앞서 생각했던 방식보다 쉽고 깔끔한데 왜이렇게 헤맸는지 나도 모르겠슴

효율성에서 떨어질까봐 긴장했는데 (채점되는동안 눈 안깜박임)

다행이 Queue써서 그런가 통과시켜주셨다 감사합니다.

 

끝~