자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 공통 원소 구하기

 

https://hyejin.tistory.com/1220

자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)]

-> 이전 문제 풀이 

 

 

 

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

 

 

문제 풀이 1

public ArrayList<Integer> solution2(int n, int[] A, int m, int[] B) {
    ArrayList<Integer> result = new ArrayList<>();
    Arrays.sort(A);
    Arrays.sort(B);

    for (int i : A) {
        for (int i1 : B) {
            if (i == i1){
                result.add(i);
                break;
            }
        }
    }

    return result;
}

👩🏻‍💻 : 먼저 배열 2개를 오름 차순으로 정렬해준 다음, 이중 for문을 돌면서 같은 값을 result 리스트에 add 하도록 했는데,, 이렇게 하면 

시간 제한에서 걸린다,, 보니까 이중 for 문을 돌면 시간 초과하는 것 같다,,, 

 

 

 

문제 풀이 2

public ArrayList<Integer> solution(int n, int[] A, int m, int[] B) {
    ArrayList<Integer> result = new ArrayList<>();
    Arrays.sort(A);
    Arrays.sort(B);
    int p1 = 0, p2 = 0;

    while (p1 < n && p2 < m) {
        if (A[p1] == B[p2]) {
            result.add(A[p1++]);
            p2++;
        } else if (A[p1] < B[p2]) {
            p1++;
        }else {
            p2++;
        }
    }

    return result;
}

👩🏻‍💻 : 그래서 저번 풀이에서 봤던 p1, p2 변수를 만들고, p1 과 p2 둘 중 하나라도 n, m 크기를 넘어가면 반복문을 종료하도록 했다. 

먼저 A[p1]과 B[p2] 가 같으면 result 리스트에 add 해주고, 그 다음 p1, p2 값을 각각 +1씩 증가해준다. 

만약 같지 않은데 A[p1]이 B[p2]보다 작으면 p1의 값을 1 증가 해주고, 그 반대일 경우에는 p2의 값을 1증가해준다.