매출액의 종류 문제에서 시간초과 에러가 뜨는데요...
224
작성한 질문수 2
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에 추가하는 식으로 변경할 수 있습니다.
위의 내용을 참조하여 코드를 한 번 다시 검토하고, 필요한 부분을 수정해 보시기 바랍니다.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
27
1
갑자기 채점 사이트가 바뀌었어요
0
32
1
문제 리스트 페이지
0
27
1
채점 사이트 관련 질문드립니다
0
23
1
봉우리 문제 질문입니다
0
81
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
64
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
72
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
67
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
85
2
6-7 강의에서
0
48
1
6-6. 장난꾸러기 질문 있습니다.
0
45
1
강의 수강후 코딩테스트
0
109
1
answer 변수 사용 여부
0
44
1
2중 for문
1
85
2
2-11. 임시반장정하기 (Runtime Error)
0
63
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
70
1
이런 풀이는 어떨까요
0
43
1
자바 스트림 방식의 효율성 질문 드립니다.
0
57
1
알고리즘 자료 구조들..
0
62
1
StringBuilder vs BufferdWriter
0
47
1
원더랜드(프림)
0
50
1
이런 코드는 어떤가요?
0
61
1
bfs 풀이
0
57
1
병합정렬
0
56
1