심사위원 시간복잡도
353
작성한 질문수 27
이렇게 작성했는데, 시간 복잡도에 걸리지 않게 작성한것이 맞나요??
import java.util.*;
class Main {
public int solution(int[] score, int k){
int answer = 0;
Arrays.sort(score);
int sum=0;
ArrayList<Integer> ans = new ArrayList<>(); //k개 원소를 담을 리스트
for(int i=0; i<score.length; i++) { //배열을 처음부터 탐색한다.
int diff = score[i+k-1] - score[i]; //앞 뒤 원소의 차이를 구한다.
if(diff<=10) { //만약 그 차이가 10이하이면
int cnt=0; //개수를 세기위한 변수
int j=i; //i번째 원소부터 시작해서 리스트에 담는다.
while(true) { //10이하의 경우에서 제일 첫번째로 찾는게 정답이다.
if(cnt==k) break; //k개만큼 담았으면 반복문 멈춘다.
ans.add(score[j++]); //답에 해당하는 원소들을 ans에 담아준다.
cnt++;
}
break;
}
}
sum=0; //원소들의 합계를 구하기 위한 변수
for(int i=0; i<ans.size(); i++) {
sum+=ans.get(i);
}
answer = (int)sum/k;
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(new int[]{99, 97, 80, 91, 85, 95, 92}, 3));
System.out.println(T.solution(new int[]{92, 90, 77, 91, 70, 83, 89, 76, 95, 92}, 4));
System.out.println(T.solution(new int[]{77, 88, 78, 80, 78, 99, 98, 92, 93, 89}, 5));
System.out.println(T.solution(new int[]{88, 99, 91, 89, 90, 72, 75, 94, 95, 100}, 5));
}
}
답변 2
0
안녕하세요, 인프런 AI 인턴이에요.
이 코드는 배열을 처음부터 탐색하며, 앞 뒤 원소간의 차이가 10 이하인 첫 k개 원소를 구하는 코드입니다. 이를 통해 k개 원소의 평균값을 구해 반환합니다.
시간 복잡도를 계산해보면, 배열을 처음부터 끝까지 한 번 순회하므로 O(n)의 시간 복잡도를 가집니다. 이후, k개의 원소를 담는 리스트에 원소를 넣는 과정은 최대 k 번 반복하므로 O(k)의 시간 복잡도를 갖습니다. 이를 종합하면 O(nk)의 시간 복잡도를 가진다고 볼 수 있습니다.
따라서, 최악의 경우 k=n 인 경우 O(n^2)의 시간 복잡도를 갖을 수 있으므로, 이 코드의 성능을 더 개선할 필요성이 있을 수 있습니다.
비밀번호
0
68
1
과일 가져가기 이러한 경우에는 반례가 생기지 않나요?
0
163
2
cpu 스케줄링
0
107
2
외부 문제 질문
0
122
2
가장 많이 사용된 회의실
0
118
2
심사위원 문제 시간복잡도 질문
0
127
1
현관문 출입순서
0
98
1
미로의 최단거리 통로
0
74
1
집으로 이동 문제 코드
0
125
1
채점 사이트 개설
0
161
2
송아지를 잡자
1
110
1
다익스트라 + 환승횟수
0
135
2
문제풀이 해설 질문입니다.
0
124
2
"이동 횟수" 문제가 변형된다면?
0
156
2
예제 3번의 정답이 이해가 되지 않아요 선생님 ㅜㅜ
0
249
1
"비밀번호" 문제 확인 부탁드립니다!
0
171
1
최대 길이 연속수열 질문
0
193
1
잃어버린 강아지 문제 count 관련 질문있습니다
0
204
1
바둑대회 질문입니당
0
222
1
5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다
0
311
1
알파코드 풀이질문입니다
0
218
1
7번 비밀 번호 문제에 시간복잡도가 궁금합니다!
0
164
1
혹시 이렇게 작성해도 괜찮나요?
0
287
2
문제풀이 확인 부탁드립니다.
0
246
1





