분석
문제는 워낙 간단하고 쉽다. 단 해당 문제의 Lesson 주제가 Time Complexity인 만큼 시간 복잡도를 최소화하는 것이 문제의 의도로 보인다.
가장 쉽게 떠올릴 수 있는 방법은 N개의 크기 배열 A를 받았을 때 (1부터 N+1)까지의 숫자를 전부 Hash의 Key로 넣고 하나씩 Remove 하는 것이다. 이렇게 하면 가장 마지막에 남는 Key가 답이 된다. 하지만 이 방법은 Hash에 넣는데 N+1번, 그리고 A배열을 순회하며 찾는데 N번 걸리므로 O(n^2)이다.
O(N)으로 끝낼 수 있는 방법은 배열을 딱 한 번만 순회하는 것이다. 처음 A 배열을 받으면 1~N+1 숫자의 합을 구한다. 그리고 A 배열을 순회하면서 합에서 값을 한 개씩 뺀다. 이렇게 하면 없는 숫자는 뺄 수 없으므로 최종 남는 숫자가 답이 된다.
Code
class Solution {
public int solution(int[] A) {
if (A.length == 0) {
return 1;
}
double n = ((double) (1 + (A.length + 1)) / 2 * (A.length+1));
for (int a : A) {
n -= a;
}
return (int) n;
}
}
'Algorithms' 카테고리의 다른 글
[Algorithms] BFS 코드 구조 (0) | 2022.06.12 |
---|---|
[프로그래머스] KAKAO RECRUITMENT 2022 신고결과받기 (0) | 2022.03.04 |
[Codility] OddOccurrencesInArray (0) | 2022.02.26 |
[Codility] CyclicRotation (0) | 2022.02.24 |
[Codility] BinaryGap (0) | 2022.02.22 |