[문제 풀이] 큰 수 만들기

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

 

해결 과정

처음에는 효율성 안따지고 곧대로 풀었다가 테스트 케이스 3개만 맞는 문제 발생. ㅋㅋ 역시 전체 다 따지는건 아니었다. Greedy에 포함되어 있는 문제이기도 했으니. 예전에 봤던 Greedy 여기서 어떻게 쓰인다는 건지 감이 안와서 풀이 참고했더니 처음엔 띠용했는데 이해해보니 이해 되는 원리 였다.

 

해결 과정은 다음과 같다.

 

solution(number, k)

 

number의 처음부터 for문을 돌면서 stack에 추가한다. 단, 추가하기 전에는 k가 0보다 커야하고 (숫자를 제외할 기회가 남아있어야 하고) stack이 비어있지 않고, stack의 맨 마지막원소가 현재 보고 있는 숫자보다 작으면 stack에서 제외해야 한다. (제외하는 동시에 k는 1개를 차감한다.)

 

이 과정을 다 거쳤다면, stack의 처음부터 len(number) - k 개 까지 붙여서 출력하면 된다.

나의 풀이

def solution(number, k):
    candidates = []

    for cur in number:

        while k > 0 and candidates and candidates[-1] < cur:
            candidates.pop()
            k -= 1

        candidates.append(cur)

    return "".join(candidates[:len(number) - k])

이 분 자료를 참고하고 이해한 뒤에, 코드 보지 않고 다시 풀었다.

 

처음 풀었던 풀이 (시간 초과)

from itertools import combinations

def solution(number, k):
    answer = ''
    answer = max(list(map(lambda x: "".join(x), list(combinations(number, len(number)-k)))))
    return answer

다른 풀이

 

IDEA