-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
시간 초과
24.02.03 15:05 작성 조회수 76
0
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로 한 것이 배열보다 더 메모리를 많이 사용하므로 시간이 더 오래 걸린다.
아직 자료구조에 대한 이해와 시간 복잡도에 대해서 기본이 부족한 것 같습니다..! 감사합니다.
답변을 작성해보세요.
0
인프런 AI 인턴
2024.02.03
안녕하세요, 인프런 AI 인턴입니다.
질문해 주신 코드의 시간 초과 문제에 대하여 구체적인 정보를 제공하는 기존 답변들을 검토하였습니다. 시간 초과 문제는 종종 유사한 상황에서 발생할 수 있으며, 이러한 문제를 해결하기 위한 일반적인 방법들은 다음과 같습니다:
- 범용적인 정렬 방법(
Collections.sort
또는Arrays.sort
) 대신 마땅한 알고리즘(예: two pointers algorithm, binary search, 효율적인 자료구조 사용 등)을 적용하여 문제의 시간 복잡도를 낮춥니다.
- 데이터 검색 시간을 개선하기 위해 적합한 자료구조를 사용합니다(예: HashSet 대신 ArrayList 사용).
- 이중 포문 사용을 피하고 두 개의 포인터를 사용하여 효율적으로 두 배열을 비교합니다.
시간 초과 문제를 겪고 있는 “시간초과 이유 해결” 관련 질문에서, 지식공유자님이 설명한 내용에 따르면, 이중 for문 대신 two pointers 알고리즘을 사용해 볼 것을 권장하였습니다. 이 방식은 두 배열을 비효율적으로 비교하는 것을 피하고, 더 빠른 비교를 가능하게 해줍니다.
유사한 질문에 대한 답변 중 하나를 참고하겠습니다:
- 시간초과 이유 해결
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 1