2021-11-20 중복되는 항목 찾기

1. O(n) 저장소 활용

 

 

값이 없으면 딕셔너리에 저장하고, 값이 있으면 그 즉시 원소를 리턴해주면 된다.

 

def find_same_number(some_list):
    container = {}
    
    for ele in some_list:
        
        if ele in container:
            return ele
        container[ele] = True

 

2. 저장소 활용하지 않고 풀기

 

 

사실 N+1 크기의 리스트에 1~N까지 자연수가 할당되려면 무조건 중복되는 놈이 하나씩 생긴다.

그 중복되는 값만 찾으면 되므로 중복되는 녀석이 있는 범위를 좁혀나가면서 구하면 될 듯 하다.

줄여 나간다는 것은 divide 한다는 것이고 이는 재귀적으로 문제를 해결해나간다는 것이다.

 

basecase : 크기가 1 

recursive : 이진분할과 같음.

 

def find_same_number(some_list, start = 1, end = None):
    
    if end == None:
        end = len(some_list)
    
    if start == end:
        return start
    
    mid = (end + start ) // 2 
    
    leftCount = 0
    
    for ele in some_list:
        if start <= ele and ele <= mid:
            leftCount += 1
        
    if leftCount > mid-start + 1:
        return find_same_number(some_list,start, mid)
    return find_same_number(some_list,mid+1, end)