[프로그래머스][stack] 사전순 부분문자열 (200903)

def solution(sentence):

    stack = []
    for alphabet in sentence:
        while len(stack) > 0 and stack[-1] < alphabet:  # 탐색 알파벳이 , 현재 스택 맨 끝보다 정렬순서작으면
            stack.pop()
        stack.append(alphabet)
    return ''.join(stack)

1. 문제 풀이

 

어떤 문자열 s가 주어졌을 때, s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 찾으려 합니다. 부분 문자열을 만드는 방법은 다음과 같습니다.

s에서 일부 문자를 선택해 새로운 문자열을 만듭니다. 단, 이때 문자의 순서는 뒤바꾸지 않습니다. 예를 들어 문자열 xyb로 만들 수 있는 부분 문자열은 다음과 같습니다.

x
y
b
xy
xb
yb
xyb

이 중 사전 순으로 가장 뒤에 있는 문자열은 yb입니다.

문자열 s가 주어졌을 때 s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 리턴하는 solution 함수를 완성해주세요.

제한 사항

• s는 길이가 1 이상 1,000,000 이하인 문자열입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

sresult

“xyb”	“yb”
“yxyc”	“yyc”

 

 

 

2. 풀이

1) 접근 자체를 잘못함.  --> ㅠㅠ

def solution(input_str):
    origin_str = input_str+''

    last_set = set(origin_str) # 전체 문자 넣기 
    last_strset = '' # 가장 정렬 큰 문자 여기다가 저장
    before_chr = ''

    for idx in range(len(origin_str)-1):
        poped_str = input_str[0:idx] + input_str[idx+1:] #하나씩 뽑힌 문자들 만들기 

        if poped_str not in last_set: # 만약 poped_str 과 중복되는게 last_strset 없다면, 
            if (last_strset == '') or (''.join(last_strset) < poped_str): 
            # 하나뽑힌 문자가, 기존 last_strset에서 정렬이 가장 큰 문자보다 더 크면, 
            
                last_strset = poped_str+'' # 업데이트
                last_set.add(last_strset)

        input_str = origin_str+'' # 뽑힌거 원래대로 다시 복구

    return last_strset
    
    ## 뭐하는 짓이지? 

스택을 안쓰고 풀려고 했다.

하나씩 문자를 뽑는 아이디어에 꽂혀서 그걸 구현하려했고... 스택으로 구현하려다 안되자 

셋에 전체, 하나씩 뽑힌애들 넣어두고 / 정렬 맨마지막에 놓인 문자를 가져오려했다... 대체 왜 그렇게 풀려고 한거지...

 

이럴 경우 발생하는 문제 

1. 'a' 또는 'aa' 경우 last_strset에 담기는게 아무것도 없다. 

2. 런타임 에러~

 

 

 

2) 스택으로 풀기 --> 하지만 크리티컬한 실수 ! 

def solution(sentence):

    stack = []
    for alphabet in sentence:
        if len(stack) > 0 and stack[-1] < alphabet:  # 탐색 알파벳이 , 현재 스택 맨끝보다 정렬순 크면
            stack.pop()
        stack.append(alphabet)
    return ''.join(stack)

스택으로 풀어야 한다. 

 

만약 입력이 xyb 라면 

alphabet : x  // stack ['x']

POP x
alphabet : y // stack ['y']
alphabet : b //  stack ['y', 'b']

 

스택의 맨 처음이 가장 큰 알파벳이 나올수 있도록, 

하지만 여기서 if len(stack) > 0 and stack[-1] < alphabet: 로 쓰게되면 문제는 

stack[-1] 만 살펴보고 그 이전은 보지 않는다는 거다. 

 

 

반례 :  acbcdd

alphabet: a // stack: ['a']
POP: a
alphabet: c // stack: ['c']
alphabet: b // stack: ['c', 'b']
POP: b
alphabet: c // stack: ['c', 'c']
POP: c
alphabet: d // stack: ['c', 'd']
alphabet: d // stack: ['c', 'd', 'd']
결과 : cdd --> c가 사라지지 않았다 !!!!!! 

 

문제는 POP 할때, if문으로 하니까 직전 알파벳 만 확인한다 

하지만 여기서 문제는 직전이 아니라 처음 인덱스까지 다 확인해야함 따라서 

while 문을 써야한다. 자기보다 정렬 순서가 더 작은 애들이 안나올때 까지 POP 하면서 돌아야함 

 

 

3) 정답 

def solution(sentence):

    stack = []
    for alphabet in sentence:
        while len(stack) > 0 and stack[-1] < alphabet:  
            # 스택 마지막이 탐색 알파벳보다 정렬 순서가 작으면 pop하며 
            # 스택 끝까지 다 돌거나 / 정렬 순서가 더 큰게 나오면 스톱
            stack.pop()
        stack.append(alphabet)
    return ''.join(stack)

 

 

분명 이 비슷한 문제들을 여러번 풀었는데 왜 저 아이디어가 생각이 안났는지 모르겠다.. 

이전 스택 문제들을 계속 복습을 해야겠는데, 

 

1) 입력 순서 그대로 둔채 / 숫자 혹은 문자 조합의 정렬이라면 --> 스택  or greedy 

 :  뽑아 가면서 앞으로 탐색 -  스택

비슷한데 숫자 조합 정렬 그리디로 푼것 : 

https://huidea.tistory.com/51?category=879544

https://huidea.tistory.com/4

 

2) 입력 숫자/문자를 계속 업데이트 하면서 정렬해야하는 상황... --> 힙힙 자료구조 

3) 리스트 인덱스 앞에서 부터 뽑아야 하는 상황이면 --> 큐 (deque 자료형태 만들고)