Level 2 큰 수 만들기 Python3

https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3 

코딩테스트 연습 - 큰 수 만들기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_큰수만들기.py

hwayeon351/Programmers-Algorithms

def solution(number, k):
    stack = []
    if k == len(number)-1: return max(number)
    for i in range(len(number)):
        if len(stack) == 0:
            stack.append(number[i])
            continue
        if stack[-1] >= number[i]:
            stack.append(number[i])
            continue
        while stack and stack[-1] < number[i]:
            stack.pop()
            k -= 1
            if k==0:
                return "".join(stack) + number[i:]
        stack.append(number[i])
    return "".join(stack[:-1])

---

풀이 과정

def solution(number, k):
    stack = []
    #한 자리 숫자만 남아야 하는 경우 number의 가장 큰 숫자만 남긴다.
    if k == len(number)-1: return max(number)
    #number의 길이 만큼 반복 -> O(n)
    for i in range(len(number)):
        #스택이 비어있는 경우 해당 숫자를 스택에 담는다.
        if len(stack) == 0:
            stack.append(number[i])
            continue
        #스택의 top에 있는 숫자보다 number[i]보다 작거나 같으면 스택에 담는다.
        if stack[-1] >= number[i]:
            stack.append(number[i])
            continue
        #스택의 top에 있는 숫자보다 number[i]가 큰 경우 스택의 top에 있는 숫자가 더 클 때까지 스택 pop -> O(n)
        while stack and stack[-1] < number[i]:
            stack.pop()
            k -= 1
            #스택 pop이 k번 일어난 경우 스택에 남겨진 문자들과 number의 i번 인덱스 이후의 문자들을 더해 return
            if k==0:
                return "".join(stack) + number[i:]
        #number[i]를 스택에 담는다.
        stack.append(number[i])
    #k = 1인 경우, 마지막 숫자를 제거한다.
    #ex) stack = 987654321
    return "".join(stack[:-1])
#시간복잡도 = O(n^2) 공간복잡도 = O(n)

 

---

오답 노트

def solution(number, k):
    answer = ''
    number = list(number)
    if k == len(number)-1: return max(number)
    while True:
    #number[I]와 number[i+1]번째 숫자 비교 후, number[i]가 작으면 number[i]를 빼고 다시 처음부터 탐색한다.
        for i in range(len(number)-1):
            if k==0:
                return "".join(number)
            if number[i] >= number[i+1]: continue
            number.pop(i)
            k-=1
            break
    return answer

처음에 접근한 방식이다. 테스트 10, 12 시간초과로 틀렸다.

0번째 인덱스부터 n-2번째 인덱스까지 for문을 반복하면서 현재 인덱스의 숫자가 다음 인덱스의 숫자보다 작은 경우 해당 인덱스의 숫자를 제거하고 for문을 벗어나서 while문 반복을 통해 다시 for문을 진행하는 방식으로 구현하였다.

시간초과가 난 경우는 while 무한루프에 빠져나오지 못했다는 것인데 그 경우는 number가 987654321일 경우이다.

이 경우에는 항상 i번째에 있는 숫자가 i+1에 있는 숫자보다 크기 때문에 숫자를 제거하지 못하기 때문이다.