leetcode 1week

 어떤 알고리즘 및 자료구조를 사용해야 효율적인지 생각해 볼 수 있어서 좋은 것 같다.

 

1. array list count 함수 사용

class Solution(object):
	def singleNumber(self, nums):
	for n in nums:
		if nums.count(n) == 1:
			return n

for문에 count 당연히 O(n제곱) 으로 성능은 좋지 않았다

2. Set 자료형의 in 이용

class Solution(object):
    def singleNumber(self, nums):
        s = set()
        for n in nums:
            if ( n in s ):
                s.remove(n)
            else:
                s.add(n)
                
        return s.pop()

set 자료형의 push/pop/in 기능을 이용하여 찾음

for문 한바퀴를 완전히 돈다. O(N)에 가까우려나

 

 

3. Array list in 이용

class Solution(object):
    def singleNumber(self, nums):
        arr = []
        for n in nums:
            if ( n in arr ):
                arr.remove(n)
            else:
                arr.append(n)
                
        return arr.pop()

Set 자료형을 사용한것과 동일한 방식으로 사용했지만 성능은 현저히 떨어졌다.

 

4. Sort 후 순차적으로 찾기

class Solution(object):
    def singleNumber(self, nums):
        nums.sort()
        size = len(nums) - 1
        
        #예외 처리 
        if(size == 0):
            return nums[0]
        if(nums[0] != nums[1]):
            return nums[0]
        if(nums[size-1] != nums[size]):
            return nums[size]
        #Loop    
        for i in range(1, size-1) :
            if nums[i-1] != nums[i] and nums[i+1] != nums[i]:
                return nums[i]

sort 후 Loop를 돌다 찾으면 탈출하기 때문에 굉장히 성능이 오락가락 하는 편이다.

 

 

---

- 역시 Array 보단 Set이 빠른 것 같다.

- 4번처럼 Loop를 돌다가 탈출하는 것보다는 2번처럼 Loop를 다 돌고 찾는 것이 안정성있는 것 같다.

  4번방식은 너무 실행시 마다 성능이 달라서.. 별로인 것 같다