[알고리즘] 가장 큰 수

https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/dashboard

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의

 

해당 강좌에 포함된 문제다.

 

 

문제

스택 문제다.

 

예제 입력에서 첫 번째 수를 s, 두 번째 수를 n이라고 할 때,

 

s에서 n개만큼 제거해서 가장 큰 수를 만드는 문제다.

 

문제 접근 방법은 스택에 차례대로 push하다가 push전에 앞에 자기보다 작은 수가 있으면 pop하고 push하면 된다.

단, pop횟수는 n번

 

강좌에 나온 풀이대로 풀었으며, 알고리즘 설명만 듣고 풀어서 강좌 답지랑 다를 수도 있다.

 

정답

s, n = tuple(input().split())

n = int(n)

arr = []
count = 0

for i in range(len(s)) :
    if i == 0 :
        arr.append(s[i])
    else :
        if count < n :
            for j in range(len(arr)-1, -1, -1) :
                if int(arr[j]) < int(s[i]) :
                    arr.pop()
                    count += 1
                    if count >= n :
                        break
                else :
                    break
            arr.append(s[i])
        else :
            arr.append(s[i])
sn = n - count

for i in range(sn) :
    arr.pop()

print(''.join(arr))

 

반응형

728x90