[스택&큐] - 가장큰수

가장큰수

 

 

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하 여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다)
만약 5276823 이 주어지고 3개의 자릿수를 제거한다면

7823이 가장 큰 숫자가 됩니다.

▣ 입력설명
첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.

▣ 출력설명
가장 큰 수를 출력합니다.

▣ 입력예제 1 5276823 3

▣ 출력예제 1 7823

▣ 입력예제 2 9977252641 5

▣ 출력예제 2 99776

 

 

 

 

 

 

 

나의 코드

arr,m=list(map(str,input().split()))
res=[]
m=int(m)

for x in arr:
    res.append(int(x))

M=max(res[0:m])

for _ in range(m):
    if res[0]<M:
        res.pop(0)
        m=m-1
cnt=0
for j in range(m):
    for i in range(j,len(res)-1):
        if res[i]<res[i+1]:
            res.insert(0,res.pop(i))
            m=m-1
            cnt+=1
            break

for _ in range(cnt):
    res.pop(0)

for _ in range(m):
    res.pop()

for x in res:
    print(x,end='')

 

어우 너무 어거지로 짜긴했는데 뭐 풀긴 풀었다.. 내가 생각해도 수레기 같은 코드네..허허 

입력 값을 받는 코드마저 엉망이다..

 

 

1. 0부터 m까지의 인덱스중 가장 큰수를 찾는다 ==> M

2. 앞자리부터 M보다 작으면 빼면서 m을 하나씩 줄인다.

3. 남은 m번(뺼수 있는 횟수)만큼 순회를 하며 m번 인덱스부터 끝까지 바로 다음 자릿값 보다 작은 수를 뺀면서 그 횟수인 cnt를 카운팅 하며 m 또한 하나씩 뺀다(3번 순회를 마친 경우 남아있는m만큼 가장 뒷 자리수들을 뺀다.). 

 

 

정답코드

import sys
sys.stdin=open("input.txt", "rt")
num, m=map(int, input().split())
num=list(map(int, str(num)))
stack=[]
for x in num:
    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))
print(res)

스택을 사용한 너무 좋은 코드 같다.

핵심은  '각 인덱스 숫자를 차례대로 스택에 넣은뒤 가장 스택위에 있는 값[-1]과 그 다음 인덱스 숫자를 비교해서 스택의 가장 뒤에 있는 값이 해당 인덱스 숫자 보다 작으면 pop()을 한다. 

그리고 남은 횟수만큼 pop()한다.

 

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

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

정수 값을 리스트로 하나씩 int형으로 변환하는 코드이다. 기억하자 !