[프로그래머스 / 그리디(Greedy) /python] 큰 수 만들기

첫 번째 코드 - 실패

 

처음 코드의 로직은

len(numbers) - k 번 만큼 (즉, 최종적으로 나오게되는 숫자의 길이만큼) 최댓값 찾는 탐색을 수행한다.

최댓값 탐색의 범위는 이전 최댓값이 나왔던 index + 1부터 현재 탐색할 수 있는 최대 영역까지이다.

 

예를 들어 만들어야 하는 숫자의 총 길이가 3이고 현재 "1234"라는 숫자 안에서 첫 번째 숫자를 선택 해야할 때,

첫 번째 숫자를 위해 탐색해야하는 영역은 "12"이다. 만들어야하는 숫자의 총 길이가 3이기 때문에 첫 번째 숫자가 선택된 이후 두 번째, 세 번째 숫자를 선택해야하는 상황까지 고려해야하기 때문이다.

def solution(number, k):
    answer = []
    start, end = 0, k + 1

    while end <= len(number):
        max_idx = get_max(start, end, number)
        answer.append(number[max_idx])
        start = (max_idx + 1)
        end += 1
    return "".join(answer)

def get_max(start, end, number): # return max index
    max_idx = start

    for i in range(start, end):
        if number[i] == 9: return i
        if number[i] > number[max_idx]:
            max_idx = i
    return max_idx

 

이렇게 열심히 로직을 설명하고 코드도 짰지만 실패했다 됴륵😥

 

테스트 코드 8번과 10번에서 실패가 나온다.. 

string concat 부분이 문제인가 싶어서 list에다가 넣어주고 join하는 방식으로 바꿔봤지만 이 방법도 효과는 없는 것 같았다.

 

 

두 번째 코드 - 실패

 

결국 구글링을 해보았는데, stack을 사용한 간단한 방법이 있었다

 

1. number의 숫자를 차례대로 빼낸다.

2. stack에 해당 숫자를 넣기 전, stack의 가장 위의 숫자를 확인한다.

 - stack 맨 위의 숫자 < number에서 빼낸 현재 숫자이면 pop 해준다.

 - 최종적으로 만들어질 숫자의 앞부분이 최대한 커야하기 때문에(stack의 밑에는 최대한 큰 숫자가 들어가야하기 때문에) 큰 숫자가 보이면 최대한 아래쪽으로 넣어주기 위해서 이 방법을 사용한다.

 

그래서 이 똑똑한 접근법을 참고해서 코드를 작성해 보았다.

 

from collections import deque
def solution(number, k):
    answer = deque([])
    answer.append(number[0])

    for i in range(1, len(number)):
        num = number[i]
        while len(answer) > 0 and k > 0 and num > answer[-1]:
            k -= 1
            answer.pop()
        answer.append(num)

    if k != 0:
        answer = answer[:-k]

    return ''.join(answer)

 

그런데... 

마지막 테케에서 런타임 에러...?ㅎㅎ... 또 실패해버렸다

 

세 번째 코드 - 성공

정말정말 모르겠다 싶어서 다른 분들의 코드를 참고해보니.... deque를 쓰냐 안쓰냐의 차이가 있었다. 그래서 deque대신 일반적인 리스트를 사용해주었는데 통과가 되었다.

def solution(number, k):
    answer = []
    answer.append(number[0])
    for i in range(1, len(number)):
        num = number[i]
        while len(answer) > 0 and k > 0 and num > answer[-1]:
            k -= 1
            answer.pop()
        answer.append(num)
        
    if k != 0:
        return ''.join(answer[:-k])
    return ''.join(answer)

 

않이.. 왜지... 사실 아직까지도 이유는 잘 모르겠다.

 

 

✔ 그리고 생각해보니 리스트를 stack처럼 사용해줄 때는 굳이 deque를 쓰지 않아도 됐었다.

python의 일반 list의 append와 pop은 O(1)이기 때문이다.