LeetCode 문제 중 난이도 Easy인 Single Number이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.
문제해석
비어있지 않은 정수 배열에서, 하나를 뺀 모든 요소들은 두개씩 들어있다. 하나뿐인 요소를 찾아라.
알고리즘은 선형시간의 복잡도(O(n))를 가져야 한다. 추가적인 메모를 사용하지 않고 가능한가?
가장 먼저 떠오른 알고리즘은 먼저 배열을 정렬 한 뒤, 배열을 처음부터 탐색해 앞이나 뒤 요소와 둘다 같지 않은 요소를 찾는 것이다.예를 들어 [1,1,2,3,3]의 경우 2가 유일한 요소로 앞의 1과도 다르고 뒤의 3과도 다르다. 코드는 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); //배열의 길이가 1이거나, 첫번째요소와 두번째요소가 다르면 첫번째요소가 single one if(nums.length==1 || nums[0]!=nums[1]) return nums[0]; //앞과 뒤 요소중 둘다 같은게 없으면 single one이므로 출력 for(int i = 1; i<nums.length-1 ; i++){ if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]) return nums[i]; } //배열을 다 돌 때까지 못찾으면 배열의 마지막요소가 single one return nums[nums.length-1]; } } | cs |
이 경우에는 추가적인 메모리 사용은 없지만 Java의 Array.sort 정렬을 하는데 최대 O(nlogn) 시간이 들므로 문제의 요구사항인 선형시간 O(n)을 초과한다.
두번째 방법은 비트연산자를 이용하는 것이다. 비트연산자를 잘 모를 경우 아래 포스팅을 참고하자.
2019/03/16 - [프로그래밍문제풀기] - 비트연산자란?
비트연산자중 ^(XOR)을 사용할 것이다. XOR연산자는 양쪽 비트가 서로 다른 경우에 1을, 같은 경우에는 0을 반환한다.
A ^ 0 = A
A ^ A = 0
A ^ B ^ A = A ^ A ^ B = 0 ^ B = B
따라서 배열의 모든 요소로 XOR 연산을 하면 두 개씩 있는 요소들은 서로 상쇄되어 사라지고 딱 하나만 있는 요소를 찾을 수 있다.
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public int singleNumber(int[] nums) { int singleone=0; for(int i = 0 ; i<nums.length ; i++){ singleone=singleone^nums[i]; } return singleone; } } | cs |
위의 코드에서 singleone이라는 정수형을 하나 추가로 사용했지만 이 경우 nums배열이 아무리 커져도 영향을 주지 않기 때문에 공간복잡도는 O(1)이고 추가적인 메모리는 사용하지 않는다고 봐도 된다.
문제 출처 - https://leetcode.com/problems/single-number
'코딩문제(LeetCode) > Easy' 카테고리의 다른 글
| 쉬프트연산자 (0) | 2019.03.18 |
|---|---|
| [코딩연습] Remove Duplicates from Sorted Array 정렬된 배열에서 중복값 제거하기 (0) | 2019.03.17 |
| 비트연산자란? (0) | 2019.03.16 |
| [코딩연습] Search Insert Position 숫자를 넣을 자리 찾기 (0) | 2019.03.14 |
| [코딩연습] Length of Last Word 마지막 단어의 길이 구하기 (2) | 2019.03.12 |
