DATA STRUCTRUE2 DAY1

1. single number
   문자열에서 같은 문자 탐색을 해서 찾으려고 했지만 느낌이 뭔가 더 쉽게 풀 수 있는 방법이 있을 것 같아서 찾아보니깐 XOR 비트 연산을 통해 빠르게 답을 구할 수 있는 문제였다.
   
   사진처럼 a와 0이 XOR 연산을 하면 a가 나오고
   a와 a가 XOR 연산을 하면 0이 나온다
   또한 교환법칙과 결합법칙이 적용된다

class Solution(object):
    def singleNumber(self, nums):
        answer = 0
        for i in nums :
            answer ^=i
        return answer

답은 배열에 요소들을 한번에 XOR 연산을 하면 된다.

2.majority-element

class Solution(object):
    def majorityElement(self, nums):
        obj ={}
        for num in nums:
            if obj[num]  :
                obj[num]+=1
            else :
                obj[num]=1
            if obj[num] >= len(nums)/2 :
                return num

처음 풀 답은 javascript 느낌으로 풀었는데
if obj[num]에서 계속 에러가 났었다.
찾아보니 python dictionary 형에서는 존재하지 않는 key값에 대해 찾을 수 없는 형태라 if문을 판별할 수 없는 것이다.
그래서

class Solution(object):
    def majorityElement(self, nums):
        obj ={}
        for num in nums:
            try:
                obj[num]+=1
            except KeyError :
                obj[num]=1
            if obj[num] > len(nums)/2 :
                return num
      

try, except KeyError 구문을 통해 조건문을 만들었고
마지막에 obj[num]> len(nums)/2를 통해 길이의 절반을 넘어가면 바로 return을 시켜서 해결했다

3.3Sum

class Solution(object):
    def threeSum(self, nums):
        output=[]
        def combination (arr, n) :
            result = []
            if n == 0 : return [[]]
            for i in range(len(arr)):
                fixed = arr[i]
                restArr = arr[i+1:]
                for k in combination(restArr,n-1):
                    result.append([fixed]+k)
            return result
        answer = combination(nums,3)
        for ans in answer:
            temp=sorted(ans)
            ans = reduce(lambda x, y: x+y, ans)
            if ans == 0:
                if temp not in output:
                    output.append(temp)
        return output

처음에 문제해결을 생각했을 때,
combination을 사용해서 3개의 수로 된 배열들을 추출하고
그 값들이 0이되는 배열을 return 했는데 답은 정확히 나왔지만 시간 초과가 떴다.
그래서 투 포인터를 활용해서 이분탐색처럼 활용해서 문제를 풀었다

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        answer = []
        
        for i in range(len(nums)) :
            if i>0 and nums[i] == nums[i-1] : continue #중복일 때는 같은 숫자로 된 배열이 생길수도 있기때문에
            result = -nums[i]
            left =i+1
            right =len(nums)-1
            while right > left :
                if nums[left]+nums[right]<result:
                    left+=1
                elif nums[left]+nums[right]>result:
                    right-=1
                else:
                    answer.append((nums[i],nums[left],nums[right]))
                    left +=1
                    right -=1
        return set(answer)

일단 배열을 오름차순으로 정렬 =>이분탐색을 위해서
배열의 요소들 중 중복된 것들을 피하기 위해서 continue로 예외처리
순회해서에 지금 i번쨰 배열 바로 다음 인덱스와 끝인덱스의 이분탐색을 통해서
1번쨰 배열의 -1을 곱한값을 찾으면 append
찾은 배열을 set형을 사용해 중복제거