• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

매출액의 종류 문제에서 시간초과 에러가 뜨는데요...

24.01.18 22:59 작성 조회수 87

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 인턴님의 프로필

인프런 AI 인턴

2024.01.20

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

rd135님의 코드를 보니, a-b 범위 내의 모든 부분 배열에 대해 매번 HashMap을 초기화하고 다시 매출액 종류를 세고 있습니다. 이렇게 되면 부분 배열마다 O(b)의 시간이 소요되어 전체적으로 O((a-b)b)의 시간 복잡도를 가지게 됩니다. 이는 a와 b가 크게 입력될 경우 시간초과를 발생시킬 수 있는 비효율적인 방식입니다.

강의에서 알려준 효율적인 방법은, 각 부분 배열에 대해 상태를 유지하며 한 칸씩 이동할 때마다 추가되는 값은 넣고, 빠지는 값은 빼는 방식으로 갱신하는 것입니다. 이를 슬라이딩 윈도우(Sliding Window) 기법이라고 합니다.

HashMap을 한 번만 사용하고, 윈도우의 시작 부분과 끝 부분이 매 이동시마다 갱신되도록 코드를 수정해야 할 것입니다. 이렇게 수정하면 각 이동마다 O(1)의 시간만 소요되어 전체적으로 O(a)의 시간 복잡도로 문제를 해결할 수 있습니다.

예를 들어, 우리가 b만큼의 윈도우를 오른쪽으로 한 칸 이동시킬 때, map에서 이전에 있던 왼쪽 끝의 숫자를 하나 감소시키고, 새로 윈도우에 포함될 오른쪽 끝의 숫자를 map에 추가하는 식으로 변경할 수 있습니다.

위의 내용을 참조하여 코드를 한 번 다시 검토하고, 필요한 부분을 수정해 보시기 바랍니다.