[python] 프로그래머스 - 가장 큰 수

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42883

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

 

 

첫 번째 풀이 : 테스트 케이스 10에서 시간 초과

 

def solution(number, k):
    answer = ''
    start = 0
    
    for i in range(k+1, len(number)+1):
        max_val = max(number[start:i])
        answer += max_val
        start += number[start:i].index(max_val) + 1

    return answer

 

난 당연히 맞을거라고 생각하고 있었는데 시간초과가 나오길래 너무 당황스러웠다.

사고방식은 다음과 같다.

 

number에서 k개를 빼므로, 반대로 len(number)-k개 만큼은 무조건 들어가야한다.

0번째부터 k+1(= len(number) - k + 1)까지 중 max를 구한다.

max값의 index를 0번째부터 k+1까지 자른 문자열에 대해 구해서 start += max_index + 1

start부터 k+2번째까지 위 수행 및 반복

 

추측키로 max와 index를 2번 사용해서 시간 복잡도에서 걸린 것 같은데

함수를 사용하는게 아닌 for문으로 max값을 구하면서 index도 같이 구하면 될 것 같다.

 

 

두 번째 풀이 : 근데 안댐

 

def solution(number, k):
    answer = ''
    start = 0
    
    for i in range(k+1, len(number)+1):
        max_val = '0'
        next_start = 0
        for index in range(start, i):
            if max_val < number[index]:
                max_val = number[index]
                next_start = index
        
        answer += max_val
        start = next_start + 1

    return answer

 

어 근데 안되넹.......모징........일단 테스트케이스 2번부터 6번까지 실패도 했고

7번부터 10번까지 시간 초과로 통과를 못했기 때문에 이 코드는 그냥 역사의 저편으로.......

 

 

세 번째 풀이 : 참고하기 참고

 

def solution(number, k):
    answer = ''
    start = 0

    for end in range(k+1, len(number)+1):
        max_val = '/'
        max_index = -1

        for index in range(start, end):
            if number[index] == '9':
                max_val = '9'
                max_index = index
                break
                
            if max_val < number[index]:
                max_val = number[index]
                max_index = index
            
        answer += max_val
        start = max_index + 1

    return answer

 

.....가는 듯 했으나 참고하기에서 힌트를 얻어서 돌아왔다.

일단 테스트 케이스 10의 초과의 원인은 max와 index 함수를 사용한 것이 원인이 맞다.

특히 max 함수에서 무지성으로 주어진 길이를 모두 탐색하기 때문에

'9'를 찾으면 어짜피 최댓값이라서 탐색을 중지하고 빠져나오는 등의 최적화를 할 수 없다.

이게 시간초과를 피하는 핵심이다.

 

테스트 케이스 2번부터 6번까지 실패한 것은 최대값을 0으로 미리 설정을 해놓아서

0에 대한 index가 반영이 안 된 것이 이유인 것 같다.

0 전의 문자를 뭐로 해야할지 모르겠어서 그냥 0으로 설정해놓고 풀었는데

이를 수정하니 정상적으로 적용되었다. 0 하나 전의 문자는 '/'이다.

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

스택을 이용한 풀이

 

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

 

1. number에서 숫자를 차례대로 가져온다

2. 가져온 수와 stack의 top값을 비교하면서 stack의 값이 작다면 작지 않을 때까지 뺀다. 빼면서 k -= 1

3. stack에 가져온 수를 넣는다.

4. 반복

5. for 탈출 후 k값이 0이 아니라면 stack에서 -k번째까지 잘라서 stack에 넣어준다.

     (k>0임에도 while 문을 돌지 않은 것이므로, stack[-1] > num 즉, stack에 담긴 값이 점차 감소하는 것이다.)

 

고찰

 

stack 풀이 같은 생각을 어떻게하지.

그리디 문제는 접근법이 너무 다양해서 풀이가 어려운 것 같다.

그리디 문제가 여태까지 중 젤 어려웠던 것 같아...