TIL_220516_스택 알고리즘

[유효한 괄호]

https://leetcode.com/problems/valid-parentheses/
괄호로 된 입력값이 올바른지 판별하라

'''
# 개인 답안
막상 작성하고 나니 분기처리가 너무 들어가서 보기가 않좋음
'''
def isValid(self, s: str) -> bool:
    stack = []
    target="()[]{}"
    for str in s:
        # 괄호 외 이상한 값이 들어오면 False 리턴
        if str not in target:
            return False
        # stack에 내용이 있으면 비교 연산
        if str in "([{":
            stack.append(str)
        elif stack:
            num = ord(stack.pop()) - ord(str)
            if num == -2 or num == -1:
                pass
            else:
                return False
        else:
            return False
    if stack:
        return False
    return True

'''
# 답안
자괴감 느낄 꺼 같음, 확실히 너무 분기처리를 남발했음
조건에서 괄호로만 입력 데이터가 구상된다는 걸 못봐서 쓸데없는 구문이 들어갔었음

key:value 형식으로 템플릿을 구성함
해당 템플릿으로 들어온 괄호가 열기인지 닫기인지를 검증

입력 데이터는 괄호로만 구성 되있기에 다른 값을 검증할 필요는 없음
in 검색은 Key를 기준으로 함으로, Key가 닫기 괄호로 되어있으니 not in은 열기 괄호인 경우 실행
열기 괄호는 바로 append가 되고,
다음 루틴에서 stack이 존재하지 않거나, 꺼낸 괄호가 들어간 내용가 일치 하지 않는 경우 False 반환
마지막에 남아있는 값이 없는지 검증해서 반환

사전 형태로 값을 정리하고 참조하는 방식은 나중에도 사용 가능 할 듯 함

'''
def isValidStack(self, s: str) -> bool:
    stack = []
    table = {
        ')': '(',
        ']': '[',
        '}': '{'
    }

    # 스택 이용 예외 처리 및 일치 여부 판별
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False
    return len(stack) == 0

[중복 문자 제거]

https://leetcode.com/problems/remove-duplicate-letters/
중복 문자 제거
중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열해라

'''
답안 1: 재귀함수

입력값은 "cbacdcbc"으로 가정
set()은 리스트를 순서 없이 중복제거를 함
sorted를 통해 새롭게 순서를 정렬해 abcd 만큼 반복문을 돌림
s.index(char)를 통해 char(현재는 a) 단어가 등장하는 시작 인덱스를 찾음
s[시작인덱스:] 를 통해 a부터 다음 내용을 suffix라는 변수로 담음 
s 중복 제거 결과와 suffix 중복제거 결과를 비교해 같으면 리턴을 진행
중복 제거한 s와 suffix를 비교하는 이유는,
넘겨받은 변수 s를 중복제거 후 정렬한 뒤 반복하는 for은 첫 루틴에서는 abcd, 다음 루틴에서는 a가 빠지고 bcd 루틴을 돔
bcd 루틴을 돌때 넘겨받은 값은 cbacdcbc 에서 a에 대한 처리가 끝나고 a 다음부터인 cdcbc 값을 넘겨받음
이때 for은 bcd 루틴을 타면서 b 루틴부터 자르기 시작 cdcbc에서 b를 기준으로 삼으면 bc가 나오며 이 값을 suffix에 저장
이때 set을 이용해 전달받은 매개변수 s의 중복 제거시 bcd가 나오며 suffix를 중복 제거시 bc가 나옴
d가 빠졋기 때문에 일치하지 않으며, 루틴상 b를 자르면 특정 요소가 소실되니, 해당 요소가 순서샅 앞이라고 판단을 함
그래서 다음 루틴인 c를 시작하며 일치하는 결과가 나와 올바른 순서가 나올때까지 루틴을 돔
return 결과에는 char+가 있어 현재 루틴에서 정확한 순서를 찾은 단어가 하나씩 반환됨
그리고 다시 함수를 호출 할때는 이미 정확한 순서를 찾은 char는 ''으로 값을 제외시키고 다시 루틴을 돔
결국 return 단어가 하나씩 쌓이면서 
b
db
cdb
acdb
순으로 쌓여가며 재귀함수를 return 함

set 함수를 배웠고,
동작 방식에 대해서는 좀더 고민을 하는 방법에 대해서 변경이 필요해보임
'''
def removeDuplicateLetters(self, s: str) -> str:
    # 집합으로 정렬
    for char in sorted(set(s)):
        suffix = s[s.index(char):]
        # 전체집합과 접미사 집합이 일치할 때 분리 진행
        if set(s) == set(suffix):
            return char + self.removeDuplicateLetters(suffix.replace(char, ''))
    return ''
    
'''
답안 2: 스택을 이용한 문자 제거
새로운 기술이 등장함

collections.Counter = 주어진 단어에 포함된 각 알파벳의 글자 수를 세어줌
사전 구조로 결과를 반환함
초기 루틴을 고민할때 사전으로 카운팅을 하는 방식을 고민했지만,
시간이 너무 오래 투자되서 포기했었음
약간 아쉬움이 남음

일단 단어가 포함 된 개수를 사전 데이터로 준비함
그 뒤 단어만큼 반복문을 진행
루틴을 시작한 단어는 개수를 차감함
처리에 대한 설명을 진행하기 전에 한가지 설명을 하자면, 
반복 루틴의 마지막에는 루틴 대상인 알파벳을 stack과 seem에 넣어줌
stack은 리스트고, seem은 집합 자료형임
집합 자료형에는 순서가 없고, 중복을 허용하지 않음

다시 처리에 대한 설명을 이어 가서,
만약 현재 문자를 이전에 본적이 있다면 처리를 생략하고 다음 문자로 넘어감
처음 보는 문자인 경우 처리를 시작함
현재 스택에 단어가 있고, 현재 단어가 스택에 마지막 단어(-1 인덱스)보다 순서가 빠르고, 스택에 마지막 단어가 아직 중복되어 있는 경우
현재 스택에 마지막 문자를 빼고 봣던 리스트에서 제거(seen.remove)함
이후 처리가 끝나면 본 리스트와 stack 리스트에 각각 추가함

즉, 예시 데이터가 cbacdcbc인 경우

c 루틴 시작
stack: 비어있음
c 문자에 대한 counter: 4
c는 이전에 본적 없음으로 처리 진행
stack이 현재 비어있기 때문에 별도 처리는 진행 안함
stack.append('c')
seem.append('c')

b 루틴 시작
stack: ['c']
b 문자에 대한 counter: 2
b는 이전에 본적 없음으로 처리 진행
stack에 내용이 존재 -- 조건 1 충족
b는 c보다 순서가 먼저임 -- 조건 2 충족
b는 카운터가 0보다 큼 -- 조건 3 충족
조건 충족으로 인해 seen과 stack에서 c를 제거
stack.append('b')
seem.append('b')

b 루틴 시작
stack: ['c']
b 문자에 대한 counter: 2
b는 이전에 본적 없음으로 처리 진행
stack에 내용이 존재 -- 조건 1 충족
b는 c보다 순서가 먼저임 -- 조건 2 충족
b는 카운터가 0보다 큼 -- 조건 3 충족
조건 충족으로 인해 seen과 stack에서 c를 제거
stack.append('b')
seem.append('b')

a 루틴 시작
stack: ['b']
a 문자에 대한 counter: 1
a는 이전에 본적 없음으로 처리 진행
stack에 내용이 존재 -- 조건 1 충족
a는 b보다 순서가 먼저임 -- 조건 2 충족
a는 카운터가 0보다 큼 -- 조건 3 충족
조건 충족으로 인해 seen과 stack에서 b를 제거
stack.append('a')
seem.append('a')

c 루틴 시작
stack: ['a']
a 문자에 대한 counter: 3
c는 이전에 본적 없음으로 처리 진행(있었지만 순서 처리 중 b에 밀려서 삭제됨)
stack에 내용이 존재 -- 조건 1 충족
c는 a보다 순서가 나중임 -- 조건 2 불충족
c는 카운터가 0보다 큼 -- 조건 3 충족
조건 불충족으로 인해 처리 안함
stack.append('c')
seem.append('c')

d 루틴 시작
stack: ['a', 'c']
a 문자에 대한 counter: 1
d는 이전에 본적 없음으로 처리 진행
stack에 내용이 존재 -- 조건 1 충족
d는 c보다 순서가 나중임 -- 조건 2 불충족
d는 카운터가 0보다 큼 -- 조건 3 충족
조건 불충족으로 인해 처리 안함
stack.append('d')
seem.append('d')

c 루틴 시작
stack: ['a', 'c', 'd']
a 문자에 대한 counter: 2
c는 이전에 본적 있음으로 처리 생략
 - 생략으로 인해 바로 다음 루틴으로 이동 -
 
b 루틴 시작
stack: ['a', 'c', 'd']
b 문자에 대한 counter: 1
b는 이전에 본적 없음으로 처리 진행
stack에 내용이 존재 -- 조건 1 충족
b는 d보다 순서가 나중임 -- 조건 2 불충족
b는 카운터가 0보다 큼 -- 조건 3 충족
조건 불충족으로 인해 처리 안함
stack.append('d')
seem.append('d')


c 루틴 시작
stack: ['a', 'c', 'd', 'b']
c 문자에 대한 counter: 1
c는 이전에 본적 있음으로 처리 생략

결국 stack에 쌓인 abdb가 join되어 반환이 됨

새롭게 Counter라는 기술을 학습했음
기존에 존재했나 여부는 집합 자료형을 이용하는 법을 배웠음
아쉽게도 답은 못내렸지만, 기술은 습득함
'''
def removeDuplicateLettersStack(self, s: str) -> str:
    counter, seen, stack = collections.Counter(s), set(), []

    for char in s:
        counter[char] -= 1
        if char in seen:
            continue
        # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)
    return ''.join(stack)

[일일 온도]

https://leetcode.com/problems/daily-temperatures/
일일 온도
매일의 화씨 온도(f) 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지 출력하라

'''
방안 1 개인답안

고민 1:
반복한다 T:
    while 이전요소 있냐? 그리고 T는 이전요소보다 따뜻한가?:
        따뜻하다 이전요소 처리해라
        얼마나 기다렸냐 = 이전요소 수만큼
    T는 이전요소로 넣어라 다음 루틴에서 검증하게
끝났다 기다린거 반환해라

이거 허점이 있음
완전 높은 온도가 아닌 중간 온도가 들어오면 기다린 범위 측정이 제대로 안됨
len이 아닌 인덱스 기반 실제 위치를 분석해야함

또한 마지막에 결국 높은 값을 찾지 못한경우 아무것도 반환하지 않음
이 문제는 append 방식을 사용했기 때문임
기본값을 0으로 준 매개변수 temperatures에 대응되는 또다른 리스트로 해결이 가능함

새로운 문제는 75 72 70 구조에서 73이 나오는 경우 72와 70은 처리가 되지만 75는 남겨짐
남겨진 채로 target에 새로운 요소가 들어오면서 문제 발생
len 방식이 아닌 index 기준으로 계산이 다시 필요

index 기준을 리스트에 다시 넣을까 고민 중이었음
생각해보니 target을 끌고 다닐 필요가 없음
해당 타겟에 index를 가지고 있으면, 값은 어차피 temperatures에서 인덱스로 찾아 갈 수 있음
값을 넣던 target 소스를 index로 변경함

'''
def dailyTemperaturesMyway(self, temperatures: List[int]) -> List[int]:
    target = []
    result = [0]*len(temperatures)
    for idx, t in enumerate(temperatures):
        if target:
            while target and temperatures[target[-1]] < t:
                result[target[-1]] = idx - target[-1]
                target.pop()
        target.append(idx)
    return result
    
'''
답안 1: 스택 값 비교
봐온 알고리즘이 조금씩 학습되서인지 답이 비슷함
다만 내 소스코드에서 target[-1]을 따로 변수에 안담아서 약간 지저분해 보이긴함
target.pop()을 홀로 그냥 빼는 용도로 사용한데 반해서 답안은 last에 담아서 알뜰하게 사용함

여유가 된다면 좀더 코드나 변수등을 정의하면서 아름답게 만들어 나가야겠음

'''
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    answer = [0] * len(temperatures)
    stack = []
    for i, cur in enumerate(temperatures):
        # 현재 온도가 스택 값보다 높다면 정답 처리
        while stack and cur > temperatures[stack[-1]]:
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)
    return answer
'''

[괄호]

https://www.acmicpc.net/problem/9012

repeat = int(input())
table ={
    ')':'(',
    ']':'[',
    '}':'{',
}
for r in range(repeat):
    target = list(input())
    result = []

    for t in target:
        if t in table.values():
            result.append(t)
        elif result and result[-1] == table[t]:
            result.pop()
        else:
            result.append(t)
    if result:
        print("NO")
    else:
        print("YES")

[스택 시퀀스]

'''
https://www.acmicpc.net/problem/1874
스택 수열
문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.
이를 계산하는 프로그램을 작성하라.

입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다.
둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다.
물론 같은 정수가 두 번 나오는 일은 없다.

출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1
1 (push)
1 2(push)
1 2 3 4 5(push)
1 2 (pop)
1 2 3(push)
1 2 3 4(psuh)

초기 생각
1부터 n까지의 수를 스택에 넣었다가.
뽑아서 그걸 쭉 펼쳐보면 그게 수열이다.
참고로 수열이라는게 그냥 나열된 규칙 같은거라고 생각하면 된다.
짝수만 펼치면 이 수열의 규칙은 짝수다 이렇게 말할 수 있다는 거다.
근데 암만봐도 이해안되서 억울해서
막말로 내가 행운에 넘버 생각하고
4 2 1 3 6 8 근본도 없는 나열을 선보이면서
"여러분 이게 수열입니다." 라고 하면 근본도 없지만 수열이 되지 않을까 생각이 든다.

그래서 일단 설명을 봤다.
1. 스택에 수를 push 할때는 오름차순으로 push
    즉, 5을 push 하고 싶으면 1, 2, 3, 4, 5 순으로 push를 해야한다.
    다음 수가 4인 경우 이미 스택에 4이 있기 때문에 자리를 비워줘야 한다.
    4, 5를 pop을 통해 제거해 주고, push를 4를 넣어줘야 한다.
2. 중요한 건 pop을 한 요소들의 순서가, 입력값의 순서와 동일해야한다.
    예를 들어 입력 값이 1, 2, 5, 3, 4 인 경우
    1 push -> 1 pop -> pop 순서 1
    1, 2 push -> 2 pop -> pop 순서 1, 2
    3, 4, 5 push -> 5 pop -> pop 순서 1, 2, 5
    3, 4 pop(3을 넣기 위해 기존 5 push할때 추가된 요소를 pop) -> pop 순서 1, 2, 5, 4, 3
    입력값 순서 와 pop 순서에 차이가 생김
    1, 2, 5, 3, 4(입력 값)
    1, 2, 5, 4, 3(pop 순서)

아무튼 이해는 끝났으니...
일단 수열을 받아 온 뒤,
수열 번호에 맞춰서 만들어질 list와
해당 list에 맞춰서 pop 되는 데이터를 보관할 공간이 필요
또한 pop, push 이벤트 시마다 기록 될 리스트에...
각 루틴이 끝날 때 마다 pop이 보관되는 리스트와 입력 값 리스트를 비교해야함...
어찌보면 간단해 보임 설명이 개같아서 그렇지

값만큼 반복한다:
    서로 같아질 때까지 반복한다:
        지금 이 값이 Stack에 있는 값보다 크냐:
            Stack에 1개씩 추가
            resulte에 push 기록
        아니면 stack에 마지막 값보다 작냐
            stack에 pop으로 낮추기
            resulte에 pop 기록
    같아졌으면 이제 검증할 시간
    pop_list랑 입력값이랑 같은 길이로 검사했을때 내용이 다르다:
        이건 실패 no 때리고 나가자! 
    
다 끝났으면 resulte 반환하자!(근데 잘못된 경우는 어떻게 판별하지?)

작업하다가 stack이 비어있는 경우 분기커리를 계속 고민하다가 깨달음
어차피 1->2->3 순차적으로 오르는 숫자니깐 리스트가 아니라 그냥 현재값만 표시하면 됨
분기처리는 일반 숫자 변수로 진행

숫자가 내려가는 분기 처리를 계속 고민하다가 깨달음
1->3->5 올라갔다가
4 이렇게 한단계씩 내려오는건 가는한데
3으로 3단계 이상은 불가능함
pop 리스트에 쌓일때
1->5->3
이렇게 되면
5->4로 내려와야하는데 이때 4가 pop 리스트에 들어오면서 그냥 

근데 루틴 맞는데 1시간정도 안되서 계속 쳐다보다가 답을 알아냄
print(NO)해야하는데 No 했다고 안됨


'''
flag = True
repeat = int(input())
result = []
stack = []
index = 1
for r in range(repeat):
    num = int(input())

    while index <= num:
        stack.append(index)
        result.append("+")
        index += 1

    if stack[-1] == num:
        stack.pop()
        result.append("-")
    else:
        flag = False
        break
if flag:
    for r in result:
        print(r)
else:
    print("NO")

[정리]

2개의 매칭된 텍스트를 다룰때는 딕셔널리를 사용하자.
특정 문자가 나온 횟수를 따질 때 Counter라는 기능을 사용하자(가능하면 분석도 하면 더 좋다)
알고리즘....갈길이 멀어보인다.
지나간 세월에 회한이 약간 들기도 하다.
현재의 집중해야지 생각이 들면서도 그때 좀더 잘 선택했더라면, 차라리 얽메이지 말고 내 길을 좀더 믿었다면 좋았을 텐데,
괜히 우물속에 빠져 이게 길이라 믿고 있었다.
물론 지나온 세월이 경험을 가져다 주었지만,
욕심에 좀더 바라고 싶어진다.
그래도 누군가에겐 배부른 소리겠지

지금 그저 할 수 있는 일을 하자