[프로그래머스 C#] Lv.2 숫자 카드 나누기

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

프로그래머스

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

- arrayA, arrayB의 최대 길이가 50만, 원소의 최대 크기가 10억으로 범위가 매우 넓음

 -> 시간 복잡도가 낮아야 함 ( 문제 특성 상 O(n)보다 낮아지긴 힘들 것 )

 

- arrayA, arrayB의 길이는 같다

 -> 동시에 체크하는 것이 유리함

 

- 문제의 조건을 보면, 한쪽만 나뉘어져야 하므로, 각 배열의 최소 값 중 적어도 하나는 나눠져야 함

 -> 가장 큰 수가 될 수 있는 최대 값은 두 배열의 최소 값 중 더 큰 값이 됨

 

주석 참조

    using System;
    using System.Collections.Generic;
    using System.Linq;

    public class Solution
    {
        public int solution(int[] arrayA, int[] arrayB)
        {
            int answer = 0;
            List<int> listA = new List<int>(); // A만 나눠져야 하는 리스트
            List<int> listB = new List<int>(); // B만 나눠져야 하는 리스트

            Array.Sort(arrayA);
            Array.Sort(arrayB);
            
            // 정렬되었기 때문에 각 0번 인덱스는 각 배열의 최소 값이 됨
            int maxValue = (arrayA[0] > arrayB[0]) ? arrayA[0] : arrayB[0];
            bool checkA, checkB; // 나뉘는 값인지 체크

            for (int i = 2; i <= maxValue; i++)
            {
                checkA = arrayA[0] % i == 0;
                checkB = arrayB[0] % i == 0;

                // 하나만 나뉘어야 하므로
                if (checkA == checkB)
                    continue;

                if (checkA)
                    listA.Add(i);
                else
                    listB.Add(i);
            }
            
            // arrayA와 arrayB의 길이만큼 한번 순회하며 조건을 체크
            for (int i = 1; i < arrayA.Length; i++)
            {
                // 예외처리
                while (listA.Contains(0)) listA.Remove(0);
                while (listB.Contains(0)) listB.Remove(0);

                // listA 지우기
                for (int j = 0; j < listA.Count; j++)
                    if (arrayA[i] % listA[j] != 0 || arrayB[i] % listA[j] == 0)
                        listA[j] = 0;

                // listB 지우기
                for (int j = 0; j < listB.Count; j++)
                    if (arrayB[i] % listB[j] != 0 || arrayA[i] % listB[j] == 0)
                        listB[j] = 0;
            }

            // 살아남은 두 list의 값 중에 최대 값이 정답이 됨
            if (listA.Count > 0)
                answer = listA.Max();

            if (listB.Count > 0 && answer < listB.Max())
                answer = listB.Max();

            return answer;
        }
    }