[Section05] Python 알고리즘 문제풀이 01~02

Q1. 가장 큰 수 : 주어진 숫자에서 m개의 숫자를 제거하여 가장 큰 수를 만들어 출력(숫자의 순서는 유지)

입력 : 숫자 m

출력 : 가장 큰 수

 

[내가 쓴 코드]

n, m = map(int, input().split())

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

result = [0] * (len(a) - m)  #최종 결과물의 자리 수 길이의 배열 생성
start = 0
pivot = len(a) - len(result)  #얘는 걍 m아님?

for i in range(len(result)) :  #비교 가능한 범위를 찾아서 첫번째 자리부터 숫자를 찾아감
    pivot += 1
    for j in range(start, pivot) :
        if result[i] < a[j] :
           result[i] = a[j]
           index = j
    start = index + 1
    
string = ""
for x in result :
    string += str(x)
    
print(string)

 

[풀이 코드]

num, m = map(int, input().split())
num = list(map(int, str(num)))  #str 해야 하나씩 접근

stack = []
for x in num :
    #stack이 존재하고 숫자를 제거할 수 있고 stack의 마지막 수가 x보다 작을 경우
    while stack and m > 0 and stack[-1] < x :  
        stack.pop()
        m -= 1
    stack.append(x)
    
if m != 0 :
    stack = stack[:-m]  #아직 지워야하는 수가 남아있을 경우 뒤부터 자르기
    
res=''.join(map(str, stack))  #stack list를 string으로 변경하여 출력
print(res)

 

 

범위를 잡아서 비교하는 과정으로 풀었음

풀이에서는 하나씩 크기를 비교하여 top에 있는 수가 더 작으면 제거 후 대신 들어감

제거 시 m -= 1하여 m == 0이 되면 나머지 수를 붙여 최종적으로 정답 도출

→ Stack 사용(Last In First Out) : 입구와 출구가 한 곳

 

---

Q1. 쇠막대기 : 쇠막대기를 레이저로 절단하여 총 막대의 개수 출력

입력 : ( ) 조합

출력 : 막대의 개수

 

[내가 쓴 코드]

a = list(input())

count = 0
result = 0

for i in range(len(a)) :
    if a[i] == ')' and a[i-1] == ')' :
        count -= 1
        result += 1
    elif a[i] == ')' :
        count -= 1
        result += count
    else :
        count += 1
    
print(result)

 

[풀이 코드]

s = input()
stack = []
cnt = 0

for i in range(len(s)) :
    if s[i] == '(' :
        stack.append(s[i])
    else :
        stack.pop()
        #레이저라면 stack top을 pop 후 stack의 길이를 막대기의 개수로 저장
        if s[i-1] == '(' :
            cnt += len(stack)
        #막대기의 끝이라면 stack top을 pop후 막대기의 개수 + 1
        else :
            cnt += 1
            
print(cnt)

 

 

 

마찬가지로 Stack 사용 문제

닫는 괄호가 발생했을 때 이전 데이터를 보고 레이저인지 막대기의 끝인지 확인하여 막대기의 개수를 계산함