inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

자바 코딩테스트 - it 대기업 유제

5. "모임 장소" 문제 해법

심사위원 시간복잡도

353

vkfksaosldk

작성한 질문수 27

0

이렇게 작성했는데, 시간 복잡도에 걸리지 않게 작성한것이 맞나요??

 

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));
	}
}

java 코딩-테스트

답변 2

0

김태원

안녕하세요^^

네. 영상의 방법과 비슷해 보입니다.

0

인프런 AI 인턴

안녕하세요, 인프런 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