[프로그래머스] <큰 수 만들기> 파이썬 풀이

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

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

"1924"에서 k가 2라면 -> 봐야하는 것 res = 2

"1924" res-1개를 제외한 나머지 중 큰 수를 찾기 (num에는 그 이후 string을 넣고, res는 1을 줄임)

"24" 큰 수 다음 인덱스부터 끝까지 res-1개를 제외한 나머지 중 큰 수 찾기

 

 

"1231234"에서 k가 3이라면 -> 봐야하는 것 res = 4

"1231234" res-1개를 제외한 나머지 중 큰 수 3 -> 3 이후를 num에 저장, res-=1

"1234" res-1개를 제외한 나머지 중 큰 수 2 -> 2 이후를 num에 저장, res-=1

res와 num 개수가 같으면 모두 answer에 append하는 예외처리

 

"4177252841"에서 k가 4라면 -> 봐야하는 것 res = 6

"4177252841" res-1개를 제외한 나머지 중 큰 수 7 -> 7 이후를 num에 저장, res-=1

"7252841" res-1개를 제외한 나머지 중 큰 수 7 -> 7 이후를 num에 저장, res-=1

"252841" res-1개를 제외한 나머지 중 큰 수 5 -> 5 이후를 num에 저장, res-=1

"2841" res-1개를 제외한 나머지 중 큰 수 8 -> 8 이후를 num에 저장, res-=1

res와 num 개수가 같으면 모두 answer에 append하는 예외처리

 

def solution(num, k):
    answer = []
    res = len(num)-k
    result = len(num)-k
    while True :
        if len(answer) == result : break
        if len(num) == res :
            answer.append(num[:])
            break
        max_idx, max_num = 0, 0
        for i in range(0,len(num)-res+1) :
            if max_num < int(num[i]) :
                max_num, max_idx = int(num[i]), i
        answer.append(num[max_idx])
        res -= 1
        num = num[max_idx+1:]


    
    return ''.join(answer)

테스트 1 〉	통과 (0.03ms, 10.4MB)
테스트 2 〉	통과 (0.05ms, 10.4MB)
테스트 3 〉	통과 (0.11ms, 10.4MB)
테스트 4 〉	통과 (0.31ms, 10.4MB)
테스트 5 〉	통과 (2.08ms, 10.4MB)
테스트 6 〉	통과 (699.72ms, 10.4MB)
테스트 7 〉	통과 (1563.68ms, 10.4MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (3.18ms, 12.1MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.03ms, 10.3MB)
테스트 12 〉	통과 (0.03ms, 10.4MB)

채점 결과

정확성: 83.3

합계: 83.3 / 100.0

 

하...

구글링해보니까 스택을 사용하면 시간이 더 빨라진다 함

 

남이 쓴 스택 코드 이해하고 집간다