★Stack & Queue & Deque Intermediate II - 3 Solved★

★ 25497 기술 연계마스터 임스 ★

import sys
input=sys.stdin.readline

N=int(input())
string=input().rstrip()
l,r,s,k,ans=0,0,0,0,0
for i in range(N):
    if string[i] in '123456789':
        ans+=1
    else:
        if string[i] == 'L':
            l+=1
        elif string[i] == 'R':
            if l==0:
                print(ans)
                sys.exit()
            else:
                l-=1
                ans+=1
        elif string[i] == 'S':
            s+=1
        else: #'K'
            if s==0:
                print(ans)
                sys.exit()
            else:
                s-=1
                ans+=1
print(ans)

 

🌿 숫자는 그대로 카운트, 다만 L 다음에 R, S 다음에 K가 오게 순서를 맞추어야 한다는 점만 주의. 순서가 꼬이면 바로 ans 출력하고 종료. L 등장할 때 마다 L 개수 += 1 하면서 R 나왔을 때 L -=1 소모하고 ans += 1. 데이터가 차례대로 순서대로 들어오고 들어온 순서부터 차례대로 처리하는 알고리즘은 스택 자료구조 동작 방식과 동일. 방식만 동일할 뿐 스택 만들 필요 없이 그 때 그 때 처리해줘도 가능.

---

★ 7585 Brackets ★

import sys
input=sys.stdin.readline
#check ()[](
while 1:
    s = input().rstrip()
    if s == '#': break
    stack=[]
    is_legal=True
    for x in s:
        if x in '([{':
            stack.append(x)
        elif x == ')':
            if stack:
                if stack[-1] == '(': stack.pop()
                else:
                    is_legal=False
                    break
            else:
                is_legal=False
                break
        elif x == ']':
            if stack:
                if stack[-1] == '[': stack.pop()
                else:
                    is_legal=False
                    break
            else:
                is_legal=False
                break
        elif x == '}':
            if stack:
                if stack[-1] == '{': stack.pop()
                else:
                    is_legal=False
                    break
            else:
                is_legal=False
                break
    print('Legal' if is_legal and not stack else 'Illegal')

 

🌿 () {} [] 쌍으로 순서대로 잘 되어 있는 지 확인. stack 만들고 해당 opened parenteses라면 바로 append, closed parentheses라면 stack[-1]과 비교. 쌍이 다르다면 바로 Illegal, 같다면 stack.pop() / stack에 아무것도 없다면 Illegal

🌿 flag 변수 적절히 활용

---

★ 31395 정렬된 연속한 부분수열의 개수 ★

import sys
input=sys.stdin.readline
N=int(input())
ns=list(map(int,input().split()))
stack=[]
ans=0
for n in ns:
    if not stack:
        stack.append(n)
        ans+=1
    else:
        if stack[-1]<n:
            ans+=(len(stack)+1)
            stack.append(n)
        else:
            stack.clear()
            stack.append(n)
            ans+=1
print(ans)

 

🌿 스택 관점으로 풀 수 있다. 일단 list왼쪽부터 돌면서 넣고자 하는 숫자를 x라 하자. stack에 아무것도 없다면 무조건 x하나 카운트 되므로 ans+=1 / 이미 stack에 존재한다면, (1) stack 맨 끝의 원소와 x 비교: 예를 들어 x가 5이고 1 2 3이 stack에 들어있을 때 stack[-1]<x이면 x를 포함해서 증가수열을 총 x 자신 포함 4개 만들 수 있다([1 2 3 5] [2 3 5] [3 5] [5]). 연속한 부분 수열만 가능하므로 len(stack) + 1만큼의 새로운 수열 개수가 추가. (2) stack[-1]>=x라면 x를 끝 원소로 사용해서 연속한 부분증가수열을 만들 수 없으므로, stack의 내용을 모두 제거하고 x 자신을 넣는다. ans += 1

---