Time Complexity - PermMissingElem

-·2022년 5월 24일
0

문제를 이해 못해서 초반에 해맸음..

처음에는 단순하게 안 이어지는걸 찾으면 되겠다고 생각함

int max = 0;
for (int i = 0; i < A.length; i++){
	if(A[i] > max) max = A[i];
}
int answer = 0;
while (max > 1){
    boolean state = false;
    for (int i = 0; i < A.length; i++){
	    if(A[i] == max) state = true;
    }
    if(!state) {
    	answer = max;
    break;
    }
    max--;
}
return answer;

주어진게 N개인 배열이면 정답은 N+1 길이가 있다고 생각하고 찾으면 된다.

처음에 이걸 파악못해서 [], [1] 이런거가 왜 틀렸는지 몰랐음

주어진게 [1] 이면

정답이 [1, 2] 라고 가정하고 찾으면 되는거 였음...

이거 깨달으니까 할만했음

일단 단순하게 루프돌리면 성능은 거의 통과못한다고 보면될듯

어짜피 답이 1,2,3...N+1 이니까

정렬시켜놓고 1,2,3.. 비교 하면 된다.

해서 이렇게 수정하니까

Arrays.sort(A);
int answer = 1;
int cnt = 0;
while (cnt < A.length){
    if(A[cnt] != cnt + 1){
        answer = cnt + 1;
        break;
    }
    cnt++;
}
if(cnt == A.length) answer = cnt + 1;
return answer;

통과~

profile
거북이는 오늘도 걷는다

0개의 댓글