[알고리즘] 3-2 공통원소 구하기 - two pointers 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/03-02
• 문제 설명 : 정수형 배열 두개가 주어졌을 때, 두 배열의 교집합을 구해 오름차순으로 정렬해 출력하는 문제

풀이

• 주어진 두 배열을 오름차순으로 정렬하고 two pointers 알고리즘을 사용하여 풀이
• 강의 풀이도 내 풀이 방식과 동일

package inflearn.tow_pointers_sliding_window;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//공통원소 구하기(two pointers 알고리즘)
public class Main3_2 {

    public static List<Integer> solution(int n, int[] nArr, int m, int[] mArr) {
        List<Integer> result = new ArrayList<>();
        int nPos = 0, mPos = 0;

        Arrays.sort(nArr);
        Arrays.sort(mArr);

        while (nPos < n && mPos < m) {

            if (nArr[nPos] < mArr[mPos]) {
                 nPos++;
            } else if (nArr[nPos] > mArr[mPos]) {
                mPos++;
            } else { //같은 값이라면
                result.add(nArr[nPos]);
                nPos++;
                mPos++;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; st.hasMoreTokens(); i++) {
            nArr[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] mArr = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; st.hasMoreTokens(); i++) {
            mArr[i] = Integer.parseInt(st.nextToken());
        }

        List<Integer> list = solution(n, nArr, m, mArr);
        for (Integer i : list) {
            System.out.print(i + " ");
        }
    }
}