728x90
반응형
출처 ) 프로그래머스
문제 설명
길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.
- 배열의 길이는 10만 이하입니다.
- 배열의 원소는 0 이상 10만 이하인 정수입니다.
[4, 1, 3, 2] | true |
[4, 1, 3] | false |
입출력 예 #1
입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다.
입출력 예 #2
[4, 1, 3]이 주어진 경우, 배열의 길이가 3이므로 배열에는 1부터 3까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3]에는 2가 없고 4가 있으므로 false를 반환하면 됩니다.
반응형
import java.util.*;
class Solution {
public boolean solution(int[] arr) {
boolean answer = true;
int[] compare = new int[arr.length];
Arrays.sort(arr); //1차적으로 정렬 먼저
for(int i = 0; i < arr.length; i++){
compare[i] = i+1;
}
if(Arrays.equals(compare, arr)){
answer = true;
} else {
answer = false;
}
return answer;
}
}
인풋 들어오는 행렬 arr은 분명 원소들이 뒤죽박죽 섞여있을 테니 1~n까지 순서대로 정렬하기 위하여 Arrays.sort
그 다음 새로 비교하기 위한 int형 행렬을 하나 만들어보자.
그리고 새로 비교한 행렬의 0번지에 1, 1번지에 2... 이런식으로 순차적으로 꽂아주자
인풋행렬에서 아다리가 맞지 않고 뭔가 빠진 게 있다면
비교를 위해 만든 compare행렬과 arr행렬을 비교했을때 분명 뻑남.
Arrays.sort의 시간복잡도 O(nlogn)
for문을 돌렸을 때 / equal 비교할 때 시간복잡도 각 O(n)
이라서 총 시간복잡도 O(nlogn)
728x90
반응형
'study > CodingTest' 카테고리의 다른 글
파이썬 반복문 누적합계 (0) | 2023.03.20 |
---|---|
자연수 뒤집어 배열로 만들기 (자료형 처리 / linkedlist / while) (0) | 2022.12.13 |
최댓값의 인덱스 구하기 (0) | 2022.10.02 |
백준 4153 직각삼각형(Java) (4) | 2022.04.26 |
백준 2480 주사위 세개(Java) (0) | 2022.04.25 |
댓글