큰 수 만들기 (프로그래머스, 레벨2)

https://programmers.co.kr/learn/courses/30/lessons/42883

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

 

첫 번째 아이디어는 조합(combinations)을 이용하는 것이다.

 

예시는 다 통과했는데 실제 테스트에서 시간 초과가 나온다. 모든 조합의 경우의 수를 리스트에 만들어서 최댓값을 뽑아오기 때문에 시간이 오래 걸리는 것 같다. 시간문제만 아니면 간단한 코드로 해결할 수 있다.

 

시간을 줄이거나 다른 방법을 생각해보자. 확실히 레벨2 부턴 쉽지 않다.

 

 

 

두 번째 아이디어는 슬라이싱을 이용해보았다.

def solution(number, k):
    temp = []
    ind = 0
    
    while k > 0:
        num = number[ind : ind + k + 1]
        m = max(num)
        a = num.index(m) + ind
        temp.append(a)
        k -= (a - ind)
        ind = a + 1
 
        if k == 1 and ind == len(number) - 1 : break
    
    answer = ''    
    for i in temp:
        answer += number[i]
    
    if k != 1:
        answer += number[temp[-1] + 1 : ]
    
    
    return answer

 

 

 

세 번째 아이디어는 큰 수를 순차적으로 찾고, 그 수의 앞에 있는 수의 개수가 k개 보다 작을 때 제거하기.

def solution(number, k):
    answer = ''
    j = 0
    h, t = 0, len(number)  		# head, tail. 밑에 for문의 시작, 끝
    while k > 0:
        if t - h == k:  		# for문의 범위에서 시작부터 끝까지 원소 개수가 k개랑 같으면 종료. 
            break
        
        mx = 0  # 최댓값
        for i in range(h, t):   # 최댓값 찾기, j는 최댓값의 인덱스
            if number[i] == '9':
                j = i
                break
            
            i_num = int(number[i])
            if i_num > mx:
                mx = i_num
                j = i       
           
        if j - h > k:   		# 최댓값 앞의 수의 개수가 k개 보다 크면 tail을 최댓값 인덱스로 바꾼다.
            t = j
        else:  					# 최댓값 앞의 수의 개수가 k개 이하면 
            answer += number[j] # 최댓값만 따로 저장
            k -= (j - h)    	# 제거한 수의 개수만큼 k의 수를 조정
            h = j + 1       	# 새로운 head는 최댓값 다음 인덱스로 조정.
            
    answer += number[h + k: ]
    
    return answer

결과는 위에서 시간초과 뜬 '테스트 10번'이 통과됐는데 위에서 아슬하게 통과한 '테스트 8번'이 시간 초과다...

아마도 원인은 다음이 아닐까 추측된다. 아래와 같은 테스트는 잘 작동하지만,

아래와 같이 같은 숫자가 많이 반복되면,

연산 횟수가 많이 늘어난다.

줄여 보려고 생각을 많이 해봤는데 잘 안된다.

 

아예 생각을 바꿔서 큰 원소를 찾아 앞에서부터 순서대로 집어넣는 방식으로 다시 code를 작성해봐야겠다.