공통원소구하기 시간초과관련

import java.util.*;

public class Main {
    public List<Integer> solution(int n, int m, int[] x, int[] y) {
        List<Integer> answer = new ArrayList<>();

        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(x[i], true);
        }
        for (int i = 0; i < m; i++) {
            if (map.containsKey(y[i])) {
                answer.add(y[i]);
            }
        }
        //오름차순 정렬
        Collections.sort(answer);
        return answer;
    }

    public static void main(String[] args) {
        Main t = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        for(int i = 0; i < n; i++){
            x[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] y = new int[m];
        for(int i = 0; i < m; i++){
            y[i] = sc.nextInt();
        }
        for(Integer i : t.solution(n,m,x,y)){
            System.out.print(i+" ");
        }
    }
}

시간복잡도 신경 쓰다가 HashMap을 사용 해봤는데 그래도 아슬하게 세이프 인 것 같습니다... 혹시 제일 좋은 방법은 없을까요?

안녕하세요, 인프런 AI 인턴입니다.

mintzberg님께서 질문하신 공통원소구하기 문제에서 시간 초과를 막기 위해 HashMap을 사용하셨지만, 여전히 성능에 대해 우려를 하고 계신 것으로 보입니다. 이와 관련하여, 유사한 질문에 대한 지식공유자의 답변을 찾아보았습니다.

해당 질문에서는 두 배열의 공통 원소를 빠르게 찾는 방법으로 “Two Pointers Algorithm”을 사용하는 것을 권장하고 있습니다. Two Pointers 기법은 두 배열을 사전에 정렬한 뒤, 각 배열을 가리키는 포인터를 이동시키면서 공통 원소를 효율적으로 찾을 수 있게 해줍니다. 아래의 문제 해결 방법을 참고하세요.

시간초과 이유 해결에서는 복잡도가 높은 이중 for-loop 대신 Two Pointers 기법을 사용하는 방법을 설명하고 있습니다. 공통 원소를 찾는 데 있어 이 방법이 HashMap을 사용하는 것보다 더 효율적일 수 있습니다.

Two Pointers 기법을 활용하기 위해서는 먼저 각 배열을 오름차순으로 정렬해야 합니다. 이후, 두 배열의 가장 앞에 위치한 요소부터 시작하여 배열의 끝까지 포인터를 이동 시키면서 공통의 원소를 찾아나갑니다. 이 때, 두 요소가 같다면 공통 원소로 판단하고, 그렇지 않을 경우 더 작은 값을 가진 배열의 포인터만 앞으로 이동시키는 것이 핵심입니다.

이 기법을 사용함으로써, 어떤 주어진 두 배열에서도 빠르게 공통 원소를 찾을 수 있으며, 시간 복잡도를 대폭 줄일 수 있습니다. HashMap을 사용한 방법도 나쁘지 않으나, 정렬과 Two Pointers 기법을 적용하여 더 좋은 성능을 얻어보는 것을 권장드립니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변