인프런 커뮤니티 질문&답변
작성한 질문수
매출액의 종류 문제에서 시간초과 에러가 뜨는데요...
작성
·
160
0
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int[] arr = new int[a];
for(int i = 0 ; i < a ; i++) {
arr[i] = in.nextInt();
}
String answer = "";
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0 ; i <= (a - b) ; i++) {
map.clear();
for(int j = i ; j < (i+b) ; j++) {
map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);
}
answer = answer + map.size() + " ";
}
System.out.println(answer);
}저는 이렇게 짰는데요...
아무리 봐도 강의에서 알려주신 것과 크게 차이를 못 느끼겠는데... 혹시 어떤 부분에서 문제가 되는걸까요?
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
rd135님의 코드를 보니, a-b 범위 내의 모든 부분 배열에 대해 매번 HashMap을 초기화하고 다시 매출액 종류를 세고 있습니다. 이렇게 되면 부분 배열마다 O(b)의 시간이 소요되어 전체적으로 O((a-b)b)의 시간 복잡도를 가지게 됩니다. 이는 a와 b가 크게 입력될 경우 시간초과를 발생시킬 수 있는 비효율적인 방식입니다.
강의에서 알려준 효율적인 방법은, 각 부분 배열에 대해 상태를 유지하며 한 칸씩 이동할 때마다 추가되는 값은 넣고, 빠지는 값은 빼는 방식으로 갱신하는 것입니다. 이를 슬라이딩 윈도우(Sliding Window) 기법이라고 합니다.
HashMap을 한 번만 사용하고, 윈도우의 시작 부분과 끝 부분이 매 이동시마다 갱신되도록 코드를 수정해야 할 것입니다. 이렇게 수정하면 각 이동마다 O(1)의 시간만 소요되어 전체적으로 O(a)의 시간 복잡도로 문제를 해결할 수 있습니다.
예를 들어, 우리가 b만큼의 윈도우를 오른쪽으로 한 칸 이동시킬 때, map에서 이전에 있던 왼쪽 끝의 숫자를 하나 감소시키고, 새로 윈도우에 포함될 오른쪽 끝의 숫자를 map에 추가하는 식으로 변경할 수 있습니다.
위의 내용을 참조하여 코드를 한 번 다시 검토하고, 필요한 부분을 수정해 보시기 바랍니다.