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

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

3-2 공통 원소 구하기(two pointers algorithm) 문제입니다.

	public List<Integer> solution(int n, int[] arr1, int m, int[] arr2) {
		List<Integer> answer = new ArrayList<>();
		Set<Integer> set = new HashSet<>();

		for(int i= 0 ; i<n; i++) {
			set.add(arr1[i])
		}
		for(int i= 0 ; i<m; i++) {
			if(!set.add(arr2[i]))
				answer.add(arr2[i]);
		}
		answer.sort((o1, o2) -> {if(o1 < o2) return -1; else if(o1 == o2) return 0; else return 1;});
		return answer;
	}

위는 제가 수업 전에 작성한 코드입니다.
1. HashSet으로 중복된 것을 거르고 List로 넣은 후에

2. List를 오름차순으로 정렬

순으로 코드를 작성했는데 마지막 테스트 케이스에 시간초과가 발생했습니다.

[ 질문 ] 

• sort때문에 시간 초과가 나는 것 같은데, 강사님 방법처럼 갖고있는 모든 원소를 sort하는 것보다 중복된 원소만 모아둔 뒤 sort하는 것이 덜 부담될 것이라 생각했는데 왜 시간초과가 나는 것인가요?

• 여기서 시간초과가 날 것이라는 것을 사전에 미리 알 수 있는 방법이 무엇일까요?