[Python] 5장 자료구조 내용 정리

• 1. 가장 큰 수(스택)
• m 개의 숫자를 제거해서 얻을 수 있는 가장 최대 값

# ch5. 1. 가장 큰 수(스택)
#n = 84836543798739827589237689348957893758937689437896743489673489673986
#d = 30

n=5276823 
d=3
stack = []

num = list(map(int, str(n)))

for x in num:
    while stack and d>0 and stack[-1]< x:
        stack.pop()
        d = d - 1
    stack.append(x)

# 다 삭제되지 않은 경우 만들어진 숫자에서 제거해주기
if d!=0: 
    stack = stack[:-d]
print(stack)

 

• 2. 쇠막대기 - 복습

# ch5 - 2. 쇠막대기
str = '(((()(()()))(())()))(()())'
stack = []
res = 0

for i in range(len(str)):
    if str[i] == '(':
        stack.append(str[i])
    else:
        stack.pop()
        if str[i-1] == '(':
            res = res + len(stack)
        else:
            res = res + 1
print(res)

 

• 3. 후위표기식 만들기

# ch5 - 3. 후위표기식 만들기
n = '3+5*2/(7-2)'
stack = []
res = ''
for x in n:
    if x.isdigit():
        res = res + x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res = res + stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and (stack[-1] != '('):
                res = res + stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and (stack[-1] != '('):
                res = res + stack.pop()
            stack.pop()

while stack:
    res = res+stack.pop()
print(res)

 

• 4. 후위식 연산

# ch5 - 4. 후위식 연산
from curses.ascii import isdigit

n = '58+65*+32+-73*-5-323*++53+2+52*-+3+'
stack = []

for x in n:
    if x.isdigit():
        stack.append(int(x))
    else:
        if x=='+' or x=='-':
            op1 = stack.pop()
            op2 = stack.pop()
            res = 0
            if x=='+':
                res = op1+op2
            else:
                res = int(abs(op1-op2))
            stack.append(res)
        elif x=='*' or x=='/':
            op1 = stack.pop()
            op2 = stack.pop()
            if x=='*':
                res = op1*op2
            elif x=='/' and op1>op2:
                res = op1//op2
            else:
                res = op2//op1
            stack.append(res)
print(stack.pop())

 

 

• 5. 공주 구하기
• 1번부터 돌아가면서 K번째 사람 제거하기

# ch5 - 5. 공주 구하기
from collections import deque
n, k = 700, 9
arr = list(range(1,n+1))
q = deque(arr)

while q:
    # k번 만큼 idx 이동하면서 값을 빼면서 idx를 찾기전 까지 바로 값을 뒤에 붙여준다.
    for _ in range(k-1):
        current=q.popleft()
        q.append(current)
    q.popleft() # k 번째 값 삭제

    # 길이가 1이 되면 마지막 원소를 출력해주고 종료한다. 
    if len(q)==1:
        print(q[0])
        q.popleft()

 

• 6. 응급실
• 우선순위 별로 치료할 때, M번째 환자의 진료 순서를 구하기

# ch5 - 6. 응급실
from collections import deque
n, m = 5, 2
risk = [60,50,70,80,90]
q = []
cnt = 0

# 우선순위 큐 생성 - index, value
for pos, val in enumerate(risk):
    q.append((pos, val))
q = deque(q) 

while True:
    # 큐에서 pop
    current = q.popleft()
    # 제일 앞의 값보다 더 큰 수가 있으면 뒤로 보낸다
    if any(current[1]<x[1] for x in q):
        q.append(current)
    # 제일 앞의 값이 가장 큰 경우
    # 진료 횟수 cnt 증가
    else:
        cnt = cnt + 1
        # 찾는 환자일 경우에 break
        if current[0] == m: 
            print(cnt)
            break

 

 

• 7. 교육과정 설계
• 사전 필수 과목을 이수하지 않으면 NO 출력
• 필수 과목을 모두 이수하지 않으면 NO

# ch5 - 7. 교육과정 설계
str = 'CBA'
n = 3
list = ['CBDAGE','FGCDAB','CTSBDEA']

stackList = []
resList = []
for i in range(len(str)):
    stackList.append(str[-i-1])
    #print(str[-i-1])

for x in list:
    preIdx = 0
    res = 'YES'
    stack = stackList.copy()
    while stack:
        search = stack.pop()
        flag = x.find(search) # 없으면 -1
        if flag != -1: # 있는 경우
            idx = x.index(search)
            if preIdx > idx:
                res = 'NO'
                break
            else:
                preIdx = idx
        else:
            res = 'NO'
            break
    resList.append(res)
print(resList)

 

 

• 8. 단어 찾기
• 1개를 제외한 모든 값들이 2번 

# ch5 - 8. 단어 찾기
n = 5
listA = ('big','good','sky','blue','mouse')
listB = ('sky','good','mouse','big')
dict = {}

for x in range(len(listA)):
    dict[listA[x]] = 1

for x in range(len(listB)):
    del(dict[listB[x]])

for key, val in dict.items():
    # print(key, val)
    print(key)

 

• 9. Anagram(아나그램)
• 순서는 다르지만, 알파벳 개수가 같은 경우 찾기

# ch5 - 9. Anagram(아나그램)
from collections import defaultdict
# ch1 = 'AbaAeCe'
# ch2 = 'baeeACA'

ch1 = 'aacccc'
ch2 = 'ccccaa'
dict1 = defaultdict(int)
dict2 = defaultdict(int)
res = 'YES'

for x in range(len(ch1)):
    dict1[x] = dict1.get(ch1[x],0)+1
    dict2[x] = dict2.get(ch2[x],0)+1
    #dict1[ch1[x]] = dict1[ch1[x]] + 1
    #dict2[ch2[x]] = dict2[ch2[x]]+ 1

for key, value in dict1.items():
    if dict2[key]!=value:
        res = 'NO'
        break
print(res)

 

 

• 10. 최소 힙 - 복습

# ch5 - 10. 최소 힙
# 최소힙 : 완전이진트리, 부모가 자식보다 작다.
import heapq as hq
n = [5, 3, 6, 0, 0, 2, 4, 0, -1]
stack = []
minVal = float('inf')

for x in n:
    if x==-1:
        break
    if x==0:
        if len(stack)==0:
            print(-1)
        else:
            print(hq.heappop(stack))
    else:
        hq.heappush(stack, x)

 

 

• 11. 최대 힙 - 복습

import heapq as hq
n = [5,3,6,0,5,0,2,4,0,-1]
stack = []

for x in n:
    if x==-1:
        break

    if x==0:
        if len(stack) ==0:
            print('-1')
        else:
            print(-hq.heappop(stack))        
            
    else:
        hq.heappush(stack, -x)