LeetCode[day1] - Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

 

Example 1:

Input: [2,2,1] Output: 1 

Example 2:

Input: [4,1,2,1,2] Output: 4

0. 내가 하고 싶은 것

 Input은 주어진 숫자들에 대해서 쌍을 이뤄서 어떤 값들이 들어있다고 한다.

 이 때, Stream 코드와 단순 코드로 해당 알고리즘을 구해보려고 한다.

 

1. 단순 코드 생각한 방법

 - 단순 코드

 우선, 문제에서 주어진 것처럼, 인풋값들은 짝을 이루는 수와 그렇지 않은 수만 있고, 이 외의 숫자는 들어오지 않는다고 명시되어 있으니, 다른 특이사항은 없는 것 같다. 그래서, 생각한 것은 Array안의 숫자들을 Map 자료구조를 활용해서 key, value로 적재하고, 해당 자료구조를 탐색을 하면 된다고 생각을 했다.

 

2. 단순 코드 작성

역시, Map을 사용했고, Map을 탐색하기 위해서 Entry로 변환한 것말고는 특별한 것이 없다.

Java 코드로 해당 로직을 더 줄일 수 있는 방법에 대해서는 더 떠오르지 않았다.

public int singleNumber(int[] nums){
  int answer = -1; //문제의 정답
  Map<Integer, Integer> map = new HashMap<>();//HashMap 자료구조 사용
  for(int num : nums){//Map에 Array의 값들을 넣어줌
      Integer boxedNum = Integer.valueOf(num);
      if(map.get(boxedNum)==null){
          map.put(boxedNum, 1);
      }else{
          map.put(boxedNum, map.get(boxedNum)+1);
      }
  }
  for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
  //Map을 Map.Entry로 변형해서, value의 값이 1개인 값에 대해서 결과를 return;
      if(integerIntegerEntry.getValue() == 1){
          answer = integerIntegerEntry.getKey();
      }
  }
  return answer;
}

 

3. 결과

4. 검색한 좋은 풀이법 1

 Map을 사용했을 때, Key에 대한 값을 누적해줬는데, 값을 누적하지 않고, put한 값을 remove하게 되면, 마지막에는 정답만 남게 된다.

public int singleNumber(int[] nums) {
	int answer = -1;
	Map<Integer, Integer> map = new HashMap<>();
		for(int num : nums){
        	Integer boxedNum = Integer.valueOf(num);
            if(map.get(boxedNum)==null){
            	map.put(boxedNum, 1);
            }else{
            	map.remove(boxedNum);
            }
		}
	answer = map.entrySet().iterator().next().getKey();
	return answer;
}

 

5. 결과

6. 검색한 좋은 풀이법 2

 정말 대단하다. xor 연산자의 특성으로 같은 값이 2번 들어오면 이전 값으로 돌아가는 성질이 있다.

그러면 정말 쉽게 해당 문제를 해결할 수 있다. 

public int singleNumber(int[] nums) {
	int answer = 0;
	for(int num : nums){
    	//처음 값이 0
        //num 1가 1번 들어올 때 : 0001
        //num 2가 1번 들어올 때 : 0011
        //num 2가 2번 들어올 때 : 0001
        //num 3가 1번 들어올 때 : 0010
        //num 3가 2번 들어올 때 : 0001
    	answer = answer ^ num; //xor 연산자
    }
	return answer;
}

 

7. 결과

8. 스트림 API 사용

 스트림 API는 내가 생각했던 아이디어를 바꾸기에 적합했다.

처음에 생각했던 내용과 같이 nums의 값들을 하나씩 돌리면서 해당 값이 몇개 있는 지 counting을 한다.

이 때, groupingBy를 사용해서 해당 값을 그룹핑한다. 그룹핑의 결과 값은 Map이다.

Map을 조회하기 위해서 entrySet으로 변형한다. 그리고 다시 해당 값들을 검사해야하기 때문에

stream()으로 변경해준다. 그리고, filter를 통해서 map.getValue() 가 1인, 하나 밖에 없는 값을 검사한다.

처음 찾은 값을 map() 메소드를 통해서 key값을 가져온다.

 Stream을 통해서 작성하고는 뿌듯했지만, 블로그에 이렇게 글을 작성하면서 느끼는 거지만, 참 구구절절하다.

성능이 당연히 안나올 수 밖에 없는 것을 알게 되었지만, Stream을 처음 도입한 좋은 기회였다.

 추후에 Stream은 계속 공부해서, 해당 결과보다 좋게 값을 구하고 싶다.

public int singleNumber(int[] nums) {
	int answer = Arrays.stream(nums)
		.boxed() //int 자료형을 Integer로 변형
		.collect(Collectors.groupingBy(number -> number, Collectors.counting())) //key에는 number, value에는 counting
		.entrySet()//groupingBy를 했을 때, return 값이 Map이기에 entrySet의 값을 사용
		.stream()//다시 stream으로 변형
		.filter(map -> map.getValue() == 1) // 그 때, map의 값이 1일 때
		.findFirst() // 처음 찾은 값, nums의 값이 보장되기 때문에 무조건 있음
		.map(Map.Entry::getKey) //얻은 값에서 key가 궁금하기 때문에
        .get(); //획득
	return answer;
}

 

9. 결과

똥 꾸지다ㅏ..