시간 초과

import java.util.*;

class Main{
	public int[] solution(int N, List<Integer> A, int M, List<Integer> B) {

		ArrayList<Integer> answer = new ArrayList<>();
		
		Collections.sort(A);
		Collections.sort(B);
		
		for(int key : B) {
			if(A.contains(key)) {
				answer.add(key);
			}
		}
		
		return answer.stream()
				.mapToInt(Integer::intValue)
				.toArray();
	}
	
	public static void main(String args[]) {
		
		Main T = new Main();
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		List<Integer> A = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			A.add(sc.nextInt());
		}
		
		int M = sc.nextInt();
		List<Integer> B = new ArrayList<>();
		for(int i = 0; i< M; i++) {
			B.add(sc.nextInt());
		}
		
		for(int answer : T.solution(N, A, M, B)) {
			System.out.print(answer + " ");
		}
		
	}		
}

안녕하세요. 이와 같이 코드를 짰는데, 케이스 4에서 시간초과가 나왔습니다.

이에 대해 저는 다음과 같은 가설을 세워봤습니다.

Collections 클래스의 sort를 하는 시간이 Arrays 클래스의 sort 시간 보다 오래 걸린다.
입력되는 배열을 ArrayList로 한 것이 배열보다 더 메모리를 많이 사용하므로 시간이 더 오래 걸린다.

아직 자료구조에 대한 이해와 시간 복잡도에 대해서 기본이 부족한 것 같습니다..! 감사합니다.

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

질문해 주신 코드의 시간 초과 문제에 대하여 구체적인 정보를 제공하는 기존 답변들을 검토하였습니다. 시간 초과 문제는 종종 유사한 상황에서 발생할 수 있으며, 이러한 문제를 해결하기 위한 일반적인 방법들은 다음과 같습니다:

범용적인 정렬 방법(Collections.sort 또는 Arrays.sort) 대신 마땅한 알고리즘(예: two pointers algorithm, binary search, 효율적인 자료구조 사용 등)을 적용하여 문제의 시간 복잡도를 낮춥니다.
데이터 검색 시간을 개선하기 위해 적합한 자료구조를 사용합니다(예: HashSet 대신 ArrayList 사용).
이중 포문 사용을 피하고 두 개의 포인터를 사용하여 효율적으로 두 배열을 비교합니다.

시간 초과 문제를 겪고 있는 “시간초과 이유 해결” 관련 질문에서, 지식공유자님이 설명한 내용에 따르면, 이중 for문 대신 two pointers 알고리즘을 사용해 볼 것을 권장하였습니다. 이 방식은 두 배열을 비효율적으로 비교하는 것을 피하고, 더 빠른 비교를 가능하게 해줍니다.

유사한 질문에 대한 답변 중 하나를 참고하겠습니다:
- 시간초과 이유 해결

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

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