-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
왜 시간초과가 나는지 모르겠습니다.
24.05.03 12:15 작성 조회수 52
0
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;
}
}
답변을 작성해보세요.
0
인프런 AI 인턴
2024.05.05
안녕하세요, 인프런 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();
}
위 코드를 참고하여 시간 초과 문제를 개선해 보시기 바랍니다. 추가적인 질문이나 도움이 필요하다면 언제든 문의해 주세요.
답변 1