[python] 해시 테이블 (2)

문제 3. 중복 문자 없는 가장 긴 부분 문자열

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라.

• ex ) 입력 : "abcabccbb" -> 출력 : 3 ( len(abc) -> 3 )
• ex ) 입력 : "bbbb" -> 출력 : 1

풀이 (슬라이딩 윈도우와 투 포인터로 사이즈 조절)

def lengthOfLongestSubstring(self,s):
    used={}
    max_length , start = 0,0
    for index, char in enumerate(s):
        # 이미 등장했던 문자라면 'start' 위치 갱신
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_length = max(max_length, index - start + 1)
        
        #현재 문자의 위치 삽입
        used[char] = index
        
    return max_length 
        

• 두개의 포인터 모두 왼쪽에서 출발한다.
• 만약 char가 used 안에 있다면, 이미 등장했던 단어이므로 start 를 used 딕셔너리의 key가 char에 해당하는 value에 1을 더해 저장한다.
• 하지만 만약 처음 등장하는 단어라면, index - start + 1와 현재의 max_length 값을 비교하고 더 큰 값을 max_length 에 저장해주면 된다.
• used[char] 는 현재 문자를 키로 하는 해시 테이블이다.
• 그러므로 , start는 이미 등장했던 문자인 경우에는 왼쪽 포인터인 start를 현재 위치까지 옮기고 아닌 경우에는 현재위치 + 1 의 위치로 옮긴다.

문제 4. 상위 K 빈도 요소

k번 이상 등장하는 요소를 추출하라.

• ex ) 입력 : nums = [1,1,1,2,2,3] , k = 2 -> 출력 [1,2]

풀이 1. Counter를 이용한 음수 순 추출

import heapq
import collections
def topKFrequent( nums,k):
    freqs = collections.Counter(nums)
    freqs_heap = []
    # 힙에 음수로 삽입
    for f in freqs:
        heapq.heappush(freqs_heap , (-freqs[f],f))
    
    topk = list()
    #k번 만큼 추출, 최소 힙이므로 가장 작은 음수 순으로 추출
    
    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])
        
    return topk

• Counter 를 이용하여 리스트 안에 있는 원소들의 개수를 세었다.
• heapq에 원소를 키/값을 바꾸어서 음수로 넣었다. 음수를 사용하면 가장 빈도 수가 높은 값이 가장 큰 음수가 된다. 그렇다면 최소 힙으로도 빈도 수가 가장 높았던 값을 추출할 수 있다.

파이썬다운 방식

def topKFrequent(nums,k):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

• zip은 여러개의 리스트를 한개의 튜플로 묶어주는 함수이다.
• • 을 통해서 언패킹해줄 수 있다.
• ex )

fruits = ['lemon' , 'pear' ,'watermelon']
for f in fruits:
    print(f, end=' ')

lemon pear watermelon

print(*fruits)

lemon pear watermelon

• 같은 결과가 나오는 것을 알 수 있다.
• 그러므로 [(1,3),(2,2)] 가 [(1,2),(3,2)]로 바뀌는 것을 알 수 있다.