[투 포인터] 2. 공통원소 구하기

2. 공통원소 구하기

 

 

설명

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

입력

첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.

두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.

네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.

각 집합의 원소는 1,000,000,000이하의 자연수입니다.

출력

두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

예시 입력 1 

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

예시 출력 1

2 3 5

 

 

<<풀이>>

시간 복잡도 : O(N)

 

나는 한 번의 수정이 있었다.

첫 번째는 이렇게 했었다.

import java.util.*;

class Main {

    public ArrayList<Integer> solution(int N, int M, int[] arr1, int[] arr2) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

       int p1 = 0, p2 = 0;
       while(p1 < N && p2 < M) {
           if(arr1[p1] < arr2[p2]) p1++;
           else p2++;

           if(arr1[p1] == arr2[p2]) {
               answer.add(arr1[p1]);
               p1++;
               p2++;
           }

       }
       return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr1 = new int[N];
        for (int i=0; i<N ; i++) {
            arr1[i] = in.nextInt();
        }
        int M = in.nextInt();
        int[] arr2 = new int[M];
        for (int j=0; j<M; j++) {
            arr2[j] = in.nextInt();
        }
        for (int x : T.solution(N, M, arr1, arr2)) {
            System.out.print(x + " ");
        }

    }
}

 

결과는 예시 값을 넣었을때 값이 2 하나만 나오며 오답이 났다. 

그래서 찾아본 결과 p1++, p2++할 때의 문제였다.

예를 들면 위에서 if문 돌 때에 p1 또는 p2를 증감시킨다. 그리고 난 뒤 밑에 있는 if문에 증감한 상태에서 한 번 더 비교하게 된다 !!

즉, 영향 받으면 안 되는데 영향을 받고 있게 된다.

이러면 내가 생각하는 알고리즘 형태가 아니게 되고, 틀리게 되는 것이다.

 

그래서 해결 방법으로 하나로 합쳤다.

import java.util.*;

class Main {

    public ArrayList<Integer> solution(int N, int M, int[] arr1, int[] arr2) {
        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

       int p1 = 0, p2 = 0;
       while(p1 < N && p2 < M) {
           if(arr1[p1] == arr2[p2]) {
               answer.add(arr1[p1]);
               p1++;
               p2++;
           } else if (arr1[p1] < arr2[p2]) {
               p1++;
           } else {
               p2++;
           }

       }
       return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr1 = new int[N];
        for (int i=0; i<N ; i++) {
            arr1[i] = in.nextInt();
        }
        int M = in.nextInt();
        int[] arr2 = new int[M];
        for (int j=0; j<M; j++) {
            arr2[j] = in.nextInt();
        }
        for (int x : T.solution(N, M, arr1, arr2)) {
            System.out.print(x + " ");
        }

    }
}

 

이렇게 했던이 결과는 정답이다. ㅎㅎ

 

최대한 투 포인터를 활용해서 구하려고 했다.

 

우선 Arrays.sort로 정렬 한 뒤에 두 점을 비교하면서 같으면 넣는 식으로 구했다. 

 

이번에는 강사님 풀이와 똑같다 ㅎㅎ