본문 바로가기

항해99 chap02

중복 문자 없는 가장 긴 부분 문자열 - 해시

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

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

입력:"abcabcbb 출력:3 설명 : 정답은 abc로 길이는 3이다.


내가 푼 코드

import heapq
from collections import deque

def solution(a):
    temp=[]
    temp=deque(temp)
    answer=[]
    for i in a:         # 들어온 문자열을 돌아간다
        if i not in temp:       #들어온 문자열이 temp에 없다면
            temp.append(i)      #삽입
        else:                   #중복이 된다면

            q =(''.join(temp))      #들어오기 전까지의 문자열로 묶음
            heapq.heappush(answer,(-len(q),q))  #answer에 문자열길이를 음수로 해서 키값으로한다

            while i in temp:        #중복되는 지점 전까지 다 삭제
                temp.popleft()
            temp.append(i)          #중복이 안되니까 삽입



    q = (''.join(temp))     # 마지막에 나온 문자까지 answer에 넣어주고 pop해주면 끝
    heapq.heappush(answer, (-len(q), q))
    #answer에 저장되어있는것중 가장 작은것이 pop되기 때문에 음수로 바까서 저장해주었으니 
    # 다시 -를 해주어 가장 길이가 긴값을 리턴
    return -heapq.heappop(answer)[0]    
a="abcabcbb"
print(solution(a))

답지

def solution(s:str):
    used={}
    max_length = start = 0
    for index, char in enumerate(s):
        if char in used and start <=used[char]: # 이미 등장했던 문자라면 START위치 갱신
            start = used[char]+1
        else:
            max_length = max(max_length,index-start+1) #최대 부분 문자열 갱신

        used[char]=index    #현재 문자의 위치 삽입
        print(used)
    return max_length

a="abcabcbb"
print(solution(a))

'항해99 chap02' 카테고리의 다른 글

그래프 DFS  (0) 2022.01.30
상위 k 빈도수 - 해시  (0) 2022.01.21
보석과 돌 - 해시  (0) 2022.01.21
스택을 이용한 큐 구현 - 큐  (0) 2022.01.21
프린터 큐 - 큐  (0) 2022.01.21