[5]알고리즘스터디 - 섹션5_2주차 스터디

파이썬 알고리즘 문제풀이 스터디 - 알까기 _ 섹션 5

문제 1 - 가장 큰 수

num ,m = map(int,input().split())
num = list(map(int,str(num)))

ans = []
for val in num:
    while ans and m and ans[-1] < val:
        ans.pop()
        m-=1
    ans.append(val)
if m>0 : # 제거할 숫자가 남았을경우 끝자리 값을 제거 
    ans = ans[:-m]
res = ''.join(map(str,ans)) #  join은 문자열로 합해주기때문에 str을 이용 
print(res)

• 연속된 숫자를 각각 하나의 숫자로 바꾸는 법 -> list(map(int,str(num)))

문제 2 - 쇠막대기

s = input()
stack = []
cnt = 0
for i in range(len(s)) :
    if s[i] == '(' :
        stack.append(s[i])
    else :
        stack.pop()
        if s[i-1] == '(' :
            cnt+=len(stack)
        else :
            cnt+=1
print(cnt)

문제 3 - 후위표기식 만들기

a = input()
stack = []
ans = ''
for x in a :
    if x.isdecimal() : # 숫자일 경우 
        ans +=x
    else : #  연산자 
        if x=='(' : # 무조건 넣은 
            stack.append('(') 
        elif x == '*' or x == '/' :
            while stack and (stack[-1]=='*' or stack[-1]=='/' ) :
                ans += stack.pop() 
            stack.append(x)
        elif x== '+' or x == '-' :
            while stack and stack[-1]!= '(':
                ans += stack.pop()
            stack.append(x)
        else : # ')' 일경우
            while stack and stack[-1]!= '(':
                 ans += stack.pop()
            stack.pop()
while stack :
    ans += stack.pop()
print(ans)

• 연속된 숫자를 각각 하나의 숫자로 바꾸는 법 -> list(map(int,str(num)))

문제 4 - 후위식 연산

s = input()
stack = []
ans = 0
for val in s :
    if val.isdecimal() : # 숫자일 경우 
        stack.append(int(val))
    else :
        first = stack.pop()
        second = stack.pop()
        if val == '+' :
            stack.append(first + second)
        elif val == '-' :
            stack.append(second- first)
        elif val == '*' :
            stack.append(first * second)
        elif val == '/' :
            stack.append (second//first )

print(stack[0])

문제 5 - 공주 구하기

from collections import deque

n,k = map(int,input().split())
nums = deque(range(1,n+1))
cnt = 0
while True :
    if len(nums) == 1 : 
        print(nums[0])
        break
    cnt+=1
    if (cnt % k)==0 : 
        nums.popleft()
    else :
        temp = nums.popleft()
        nums.append(temp)

• 내가 만든 코드

강사님의 코드

from collections import deque

n,k = map(int,input().split())
dq = list(range(1,n+1))
dq = deque(dq)
while dq :
    for _ in range(k-1) :
        cur =  dq.popleft()
        dq.append(cur)
    dq.popleft()
    if len(dq) == 1 : 
        print(dq[0])
        dq.popleft()

• cnt를 count하지않고 k-1 전까지 돌리고 pop한다.
• while True가 아닌 deque가 존재하는 동안 while문을 돌린다.

문제 6 - 응급실

from collections import deque

n,m = map(int,input().split())
dq =  [(pos,val) for pos ,val in enumerate(list(map(int,input().split())))]
dq = deque(dq)
cnt = 0
while True :
    cur = dq.popleft()
    if any(cur[1] < x[1] for x in dq)  : # 한명이라도 있다면
        dq.append(cur)
    else : # 진료한다.
        cnt+=1
        if cur[0] == m :
            print(cnt) 
            break

• 처음 지정된 숫자를 어떻게 기억해야할지 몰랐는데 enumerate를 사용한다.
• 덱의 모든 숫자와 비교하여 큰지 알아야할 때 for문을 이용하여 비교한다.

문제 7 - 교육과정 설계

<내가 푼 풀이>

from collections import deque

order = input()
n = int(input())
for i in range(n) :
    cnt = 0
    isTrue = False 
    dq=deque(input())
    for j in dq :
        if cnt < len(order) and j == order[cnt] :
            cnt+=1
    if cnt == len(order) : isTrue = True
    print('#%d %s' %(i+1,'YES 'if isTrue else 'NO'))

• deque을 특징을 크게 이용하지않고 풀이하였다.

문제 8 - 단어찾기

n = int(input())
dict1 = {} # 딕셔러니 
for _ in range(n) :
    tmp =input()
    dict1[tmp] = 0

for _ in range(n-1) :
    tmp =input()
    dict1[tmp] = 1

for key ,val in dict1.items() :
    if val == 0 :
        print(key)

문제 9 - 아나그램 [딕셔너리 해쉬]

a = input()
b = input()

str1 = dict()
str2 = dict()

for x in a :
    str1[x] = str1.get(x,0) + 1

for x in b :
    str2[x] = str2.get(x,0) + 1

for i in str1.keys() : 
    if i in str2.keys() : # 키가 str2에도 존재 
        if str1[i]!= str2[i] : # 개수가 다르다면
            print("NO")
            break
    else : # 키가 존재 X
        print("NO")

else : # for문의 정상적인 종료 
    print("YES")

 

<개선된 아나그램>

a = input()
b = input()

str = dict()
for x in a :
    str[x] = str.get(x,0) + 1
for x in b :
    str[x] = str.get(x,0) - 1    

for x in a :
    if str[x] != 0 :
        print("NO")
        break
else : print("YES")

[C++의 해쉬처럼]

a = input()
b = input()

str1 = [0]*52 # 알파벳의 개수 (대+소)
str2 = [0]*52
for x in a :
    if x.isupper() : # 대문자라면  
        str1[ord(x)-65 ] +=1 # ord == 아스키 숫자로 반환하는 함수 
    else : 
        str1[ord(x)-71 ] +=1 

for x in b :
    if x.isupper() : # 대문자라면  
        str2[ord(x)-65 ] +=1 # ord == 아스키 숫자로 반환하는 함수 
    else : 
        str2[ord(x)-71 ] +=1 

for i in range(52) :
    if str1[i] != str2[i] :
        print("NO")
        break
else :
    print("YES")

• 대문자와 소문자를 모두 합해 52개 (26+26)
• 대문자는 65-90, 소문자는 97-122이다.
• 대문자는 65를 빼고, 소문자는 71을 뺀다.

문제 10- 최소힙

import heapq as hq

a = []
while True :
    x = int(input())
    if x == -1 : break
    if x == 0 :
        print(hq.heappop(a)) # list a에서 루트값을 pop
    else : 
        hq.heappush(a,x)

문제 11- 최대힙

import heapq as hq

a = []
while True :
    x = int(input())
    if x == -1 : break
    if x == 0 :
        print(-(hq.heappop(a))) # list a에서 루트값을 pop
    else : 
        hq.heappush(a,-x)