왜 시간초과가 나는지 모르겠습니다.
254
작성한 질문수 6
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class 매출액의_종류 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = scan.nextInt();
}
System.out.println(mySol(n,k,arr));
}
private static String mySol(int n, int k, int[] arr) {
String result = "";
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<k-1;i++){
map.put(arr[i],map.getOrDefault(arr[i],0) + 1);
}
int lt = 0;
for(int rt=k-1;rt<n;rt++){
map.put(arr[rt],map.getOrDefault(arr[rt],0) + 1);
result += map.size() + " ";
map.put(arr[lt], map.get(arr[lt]) - 1);
if(map.get(arr[lt]) == 0) map.remove(arr[lt]);
lt++;
}
return result;
}
}답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
님의 코드가 시간 초과가 나는 원인은 매번 연속적인 k개의 수를 처리할 때, HashMap을 재사용하여 매번 map.size()를 호출하는 과정에서 발생할 수 있습니다. 하지만 님의 접근 방식은 기본적으로 올바르며, sliding window와 HashMap을 사용하여 문제를 해결하려는 시도는 좋습니다.
문제는 주어진 범위에서 처리할 데이터의 양이 많을 때, HashMap의 연산과 결과 문자열의 연산이 오버헤드를 발생시키며 이로 인해 시간 초과가 발생할 수 있습니다. 특히, 결과를 문자열에 누적하는 방식(result += map.size() + " ";)은 매 연산마다 새로운 문자열 객체를 생성하므로, 이 부분도 시간 초과에 기여할 수 있습니다.
시간 초과 문제를 해결하기 위한 몇 가지 방법을 제안드립니다:
- StringBuilder를 사용하여 결과를 누적합니다. StringBuilder는 문자열을 더할 때 새로운 객체를 생성하지 않으므로 더 효율적입니다.
- 가능하다면, 문제의 요구사항을 다시 검토하여 더 효율적인 알고리즘을 고민해 보세요. 예를 들어, 더 빠른 조회를 위해 다른 자료 구조의 사용을 고려하거나, 알고리즘을 최적화 할 수 있는지 검토해 보세요.
private static String mySol(int n, int k, int[] arr) {
StringBuilder result = new StringBuilder();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < k - 1; i++) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
}
int lt = 0;
for (int rt = k - 1; rt < n; rt++) {
map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 1);
result.append(map.size()).append(" ");
map.put(arr[lt], map.get(arr[lt]) - 1);
if (map.get(arr[lt]) == 0) map.remove(arr[lt]);
lt++;
}
return result.toString();
}
위 코드를 참고하여 시간 초과 문제를 개선해 보시기 바랍니다. 추가적인 질문이나 도움이 필요하다면 언제든 문의해 주세요.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
21
1
갑자기 채점 사이트가 바뀌었어요
0
29
1
문제 리스트 페이지
0
25
1
채점 사이트 관련 질문드립니다
0
23
1
봉우리 문제 질문입니다
0
79
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
63
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
70
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
67
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
84
2
6-7 강의에서
0
47
1
6-6. 장난꾸러기 질문 있습니다.
0
43
1
강의 수강후 코딩테스트
0
106
1
answer 변수 사용 여부
0
43
1
2중 for문
1
84
2
2-11. 임시반장정하기 (Runtime Error)
0
63
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
69
1
이런 풀이는 어떨까요
0
42
1
자바 스트림 방식의 효율성 질문 드립니다.
0
56
1
알고리즘 자료 구조들..
0
60
1
StringBuilder vs BufferdWriter
0
47
1
원더랜드(프림)
0
48
1
이런 코드는 어떤가요?
0
59
1
bfs 풀이
0
56
1
병합정렬
0
55
1