개발관련
[codility] MissingInteger
hjaelife
2023. 8. 21. 13:21
(문제) A 배열이 주어질 때, 빠진 자연수 찾기



(my solution)
- 처음에는 Bubble Sorting을 통한 정렬 후 missingInteger를 찾는 방향으로 짰다.
- 왜냐하면 int A = {3, 4, 5} 일 때 6이 반환된다고 생각했기 때문 (하지만 이런 형태로 A가 주어지는 경우는 없다.)
- 그냥 단순하게 배열을 순회하면서 HashSet에 값을 넣고, 1부터 증가시켜 가면서 빠진 값을 리턴해주면 끝난다.
- 결론: 불필요한 케이스를 생각했고 단순한 문제를 복잡하게 풀었다.
- 시간 복잡도는 O(N^2) --> O(N)으로 감소했다.
- 이참에 정렬 복습이나 해야겠다.
package codility.tasks;
import java.util.HashSet;
public class MissingInteger {
public static int solution(int[] A) {
HashSet<Integer> founded = new HashSet<>(A.length);
for (int num : A) {
founded.add(num);
}
int i;
for (i = 1; i < A.length + 1; ++i) {
if (!founded.contains(i)) {
return i;
}
}
return i;
}
}
(chat GPT)
- 내가 푼 방식과 동일하다.
- 디테일이지만 두 번째 반복문에서 i의 반복조건을 i <= A.length + 1 로 두는 게 더 좋은 것 같다.
- 왜냐하면
1. return 값이 i와 -1로 나눠져서 다른 케이스라는 게 이해가 더 잘 됨
2. int i를 for문에서 선언할 수 있어서 불필요한 라인이 줄어듬
import java.util.HashSet;
class Solution {
public int solution(int[] A) {
HashSet<Integer> seen = new HashSet<>();
for (int num : A) {
if (num > 0) {
seen.add(num);
}
}
for (int i = 1; i <= A.length + 1; i++) {
if (!seen.contains(i)) {
return i;
}
}
return -1;
}
}