[인프런 알고리즘] Chapter 3, 2번 문제(공통원소 구하기)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class sec03_02 {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2) {
        ArrayList<Integer> integers = new ArrayList<>();
        HashMap<Integer, Boolean> map = new HashMap<>();

        for (int i : arr1) map.put(i, false);
        for (int i : arr2) if(map.containsKey(i)) integers.add(i);
        Collections.sort(integers);

        return integers;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr2 = new int[M];
        for(int i = 0; i < M; i++) arr2[i] = Integer.parseInt(st.nextToken());

        for (Integer i : solution(arr, arr2)) System.out.print(i + " ");
    }
}

 

두 번째 코드(투 포인터)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec03_02 {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2) {
        ArrayList<Integer> integers = new ArrayList<>();
        Arrays.sort(arr1); Arrays.sort(arr2);
        int ptr1 = 0, ptr2 = 0;
        
        while (ptr1 < arr1.length && ptr2 < arr2.length)
        {
            if (arr1[ptr1] == arr2[ptr2])
            {
                integers.add(arr1[ptr1]);
                ++ptr1;
                ++ptr2;
            }
            else if (arr1[ptr1] < arr2[ptr2]) ++ptr1;
            else if (arr1[ptr1] > arr2[ptr2]) ++ptr2;
        }

        return integers;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr2 = new int[M];
        for(int i = 0; i < M; i++) arr2[i] = Integer.parseInt(st.nextToken());

        for (Integer i : solution(arr, arr2)) System.out.print(i + " ");
    }
}

 

설명

두 번째 코드(투 포인터)에 대한 설명

• 두 배열 arr1과 arr2를 정렬한다.
• 두 배열의 포인터 ptr1과 ptr2를 초기화한다.
  
  
• 두 포인터를 이동시키면서 공통된 원소를 찾는다.
  - arr1[ptr1]와 arr2[ptr2]가 같으면 해당 원소를 결과 리스트에 추가하고 두 포인터를 모두 증가시킨다.
  - arr1[ptr1]가 arr2[ptr2]보다 작으면 ptr1을 증가시킨다.
  - arr1[ptr1]가 arr2[ptr2]보다 크면 ptr2를 증가시킨다.
  
  
• 두 포인터 중 하나가 배열의 끝에 도달할 때까지 위 과정을 반복한다.
• 결과 리스트를 반환한다.