[Algorithm] Two pointers 알고리즘을 이용하여 공통원소 구하기

문제

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요. (각 집합안의 원소는 중복되지 않는다.)

 

입력 예시

5
1 3 9 5 2
5
3 2 5 7 8

 

출력 예시 

2 3 5

 

일단 내가 짠 코드는 이중 for문을 이용하여 n과 m이 각 리스트의 원소의 수라고 하였을 때 시간복잡도가 O(n*m)이었다. 그랬더니 리스트별로 데이터가 각 30000개일 경우 타임아웃 오류가 났다. 제한이 1000ms인데 1700ms인가.. (머쓱..)

 

투포인터 알고리즘을 이용한다면 시간복잡도가 O(n+m)이 되게 된다. 이 방법으로 타임아웃 에러를 해결할 수 있었다. 

이중 for문

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private String solution(int n, int[] list, int m, int[] list2) {
        ArrayList<Integer> answerList = new ArrayList<>();
        String answer = "";
        
        if(n > m) {
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(list2[i] == list[j]) {
                        answerList.add(list2[i]);
                        break;
                    }
                }
            }
        } else {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(list[i] == list2[j]) {
                        answerList.add(list[i]);
                        break;
                    }
                }
            }
        }

        // 공통 원소를 정렬
        for(int k = 0; k < answerList.size()-1; k++) {
            int leastIndex = k;
            for(int l = k+1; l < answerList.size(); l++) {
                if(answerList.get(leastIndex) > answerList.get(l)) {
                    leastIndex = l;
                }
            }

            answer += answerList.get(leastIndex) + " ";

            int tmp = answerList.get(k);
            answerList.set(k, answerList.get(leastIndex));
            answerList.set(leastIndex, tmp);
        }

        answer += answerList.get(answerList.size()-1);

        return answer;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main main = new Main();

        int n = scanner.nextInt();
        int[] list = new int[n];
        for(int i = 0; i < n; i++) {
            list[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        int[] list2 = new int[m];
        for(int j = 0; j < m; j++) {
            list2[j] = scanner.nextInt();
        }

        System.out.println(main.solution(n, list, m, list2));
    }
}

 

부끄럽지만 정렬이 되어있지 않은 두 리스트 중에 한 짧은 리스트를 첫번째 for문, 더 큰 리스트를 두번 째 for문 안에 넣어 일치할 경우 답에 추가하고 break하도록 반복한 후,

최종적으로 공통 원소가 들어있는 리스트를 선택 정렬을 이용하여 정렬하도록 한 코드이다,,,

이게 계속 타임아웃 에러가 발생하였던 코드이다. 

 

Two Pointers를 이용한 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private String solution(int n, int[] list, int m, int[] list2) {
        Arrays.sort(list);
        Arrays.sort(list2);
        String answer = "";
        int p1 = 0, p2 = 0;

        while(p1 < n && p2 < m) {
            if(list[p1] == list2[p2]) {
                answer += list[p1++] + " ";
                p2++;
            } else if(list[p1] < list2[p2]) {
                p1++;
            } else {
                p2++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main main = new Main();

        int n = scanner.nextInt();
        int[] list = new int[n];
        for(int i = 0; i < n; i++) {
            list[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        int[] list2 = new int[m];
        for(int j = 0; j < m; j++) {
            list2[j] = scanner.nextInt();
        }

        System.out.println(main.solution(n, list, m, list2));
    }
}

 

우선 이 코드는 Arrays.sort메서드를 활용하여 두 리스트를 오름차순으로 정렬한 후, 두 배열을 각각 가리킬 p1, p2 포인터를 생성한다. 만약 일치한다면 둘 다 +를 해주고, 일치하지 않는데 인덱스에 해당하는 배열 값이 작을 경우 작은 인덱스를 +해주는 시간복잡도가 O(n+m)인 알고리즘이다.

 

 

대충 이런 플로우로 가는 것이다. 그래서 원래의 알고리즘과 달리 n+m번만 반복하면 정렬된 공통된 원소 리스트를 가질 수 있다. 재작년에 알고리즘 수업때 배웠는데 이제서야 기억이 나는 나,,,, 정신차리쟈!!! 엄교수님 감사합니다