CODE KATA #29

공통 원소 찾기

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 각 집합의 원소는 1,000,000,000이하의 자연수입니다.

나의 풀이

            function solution(arr1, arr2){
                let answer=[];
                let m = arr1.length;
                let i = 0;
                while (i<m) {
                    if (arr2.indexOf(arr1[i])!== -1) answer.push(arr1[i]);
                    i++;
                }
                answer.sort();
                return answer;
            }
            
            let a=[1, 3, 9, 5, 2];
            let b=[3, 2, 5, 7, 8];
            console.log(solution(a, b));

정답 풀이

            function solution(arr1, arr2){
                let answer=[];
                arr1.sort();
                arr2.sort();
                let p1=p2=0;
                while(p1<arr1.length && p2<arr2.length){
                    if(arr1[p1]==arr2[p2]){
                        answer.push(arr1[p1++]);
                        p2++;
                    }
                    else if(arr1[p1]<arr2[p2]) p1++;
                    else p2++;
                }              
                return answer;
            }
            
            let a=[1, 3, 9, 5, 2];
            let b=[3, 2, 5, 7, 8];
            console.log(solution(a, b));

깨달은 점

정답 풀이가 굳이 저 방식을 고수한 점이 이해가 가지 않았다.

• 왜 arr1과 arr2를 사전에 정렬한 후에 시작하였을까?
• 나의 풀이가 더 간단한 방식으로 보임에도 불구하고 저 방식을 사용한 이유?

두가지에 대하여 생각을 해본 결과, 특정 a,b가 주어지는 경우 정답 풀이가 더 빠를 수 있지만 나의 풀이가 더 빠른 경우도 많다. 특히, a의 길이가 짧은 테스트 케이스의 경우 그 점이 두드러지는데, 이러한 극단적인 상황을 최소화 하고자 해당 방식을 사용한 것 같다. 하지만 이 문제에서 나의 풀이가 아닌 정답 풀이가 정답으로 정해진 이유는,

특정 상황에서 더 빠른 것보다 어떠한 상황에도 적당히 빠른 것이 더 나은 코드이기 때문이다

라는 결론을 얻었다. 따라서 앞으로도 알고리즘 문제 풀이를 함에 있어서 해당 사항을 명심하고 풀이를 진행해야겠다.