6.20 미경이 스터디

Photo by Pietro Mattia on Unsplash

큰 수 만들기

def solution(numbers, k):
    answer = []
    i = 0
    while k > 0:
        if len(numbers) -1 == i or numbers[i] < max(numbers[i+1:i+k+1]):
            k-=1
        else:
            answer.append(numbers[i])
        i+=1
    return ''.join(answer)+ numbers[i:]

내가 이해한 룰

1. 주어진 K개의 숫자를 뺀다. = len(numbers) - k개의 숫자를 선택한다.
2. k개의 숫자를 빼고 난 후 가장 큰 수를 만드는 법을 만들어라(숫자를 빼기만 해서 순서변경X)

문제풀이

1. 가장 큰 수를 만들기 위해서는 (k개를 제거하고 앞에 있을 수 있는) 가장 큰수가 앞쪽에 배치될 수 있도록 해야한다.
2. 예를들어 문제에서 제시된 4177252841에서 가장 큰 수는 8이지만 8 뒤는 3자리 밖에 남지 않아서 8은 제일 앞 수가 될 수 없다.
3. 두번째로 큰 7은 앞 두자리를 제거해도 k의 여유가 있고 뒷자리의 여유도 충분하다.
4. 현재 값과 바로 뒷 인덱스의 값을 비교하여 결과물을 도출하려고 했으나 시간초과로 실패했다.
5. 다음 바로 시도한 코드가 위에 있는 코드인데 시간이 조금 줄어들긴 했어도 여전히 시간초과가 나왔다.

def solution(numbers, k):
    answer = []
    for number in numbers:
        while answer and answer[-1] < number and k > 0:
            answer.pop()
            k-=1
        answer.append(number)
    if k > 0:
        answer = answer[:-k]
    return ''.join(answer)

다른 사람들의 풀이를 참고하여 고쳐본 코드이다. 속도면에서 엄청나게 차이를 보인다. 스택을 쌓아서 만들고자하는 생각에는 닿았지만 answer에 값이 없는 상황을 먼저 while 조건에 넣고 없을 때는 그냥 append로 넣어주는 부분을 생각하지 못해 긴 시간을 헤맸고 결국 다른 분들의 답을 볼 수밖에 없었다. 우선 튜터님께서 조언해주신대로 시간 안에 못 풀면 스트레스 받지말고 답을 보고 답을 쓴 사람들의 로직을 훔쳐서 내 것으로 만드는 것이 좋을 것 같다.

생각해볼 것들

number = number[:i] + number[i+1:] 같이 변수를 슬라이싱으로 새롭게 할당하는 식은 빠르게 값을 얻어야 하는 로직에서는 피하는게 좋을듯하다. (사실 보기에도 그렇게 좋은 코드는 아니어서 앞으로 피하려고 한다.)