프로그래머스 - 큰 수 만들기(파이썬, LV2) / 그리디(Greedy)

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

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

이 문제는 그리디로 현재 최상의 값을 계속 골라나가면 된다.

그런데, 최상의 값을 찾기 위한 탐색 범위를 계속 한정지어서 풀려고 했다.

그러나 그렇게 풀어버리니 아래 테스트 케이스의 시간 복잡도를 극복하지 못했다. O(N^2)이 되버린 것이다.

"INPUT"
number = "1234567890"*100000
k = 999999

"OUTPUT"
answer = "99999...."

그래서 결국 다른 풀이를 찾아봤다. (출처 : scarletbreeze의 블로그)

핵심은 O(N)이 되도록 문자열을 한 번씩 파싱하는 것이다.

 

만약 제거해야되는 수(k)가 남아있고(>0)

내가 가장 최근에 추가했던 숫자(answer[-1])보다 지금 파싱하는 숫자(num) 보다 클 경우 

숫자(answer[-1])를 제거한다.

 

이런식으로 전체를 파싱하다가 더 이상 제거할 숫자가 없으면(k==0)

남은 후보들(number[i:])을 그대로 추가한다.

 

그런데 고려해야할 경우가 있다. 

"INPUT"
number = "987654321"
k = 8

"OUTPUT"
answer = "9"

이 경우, 값을 계속 추가하고 빼주지 못해서 결과값이 987654321로 나온다.

왜냐하면, 최근에 추가했던 숫자보다 지금 파싱하는 숫자보다 무조건 크기에 빼는 경우가 없었기 때문이다.

그래서 계속 추가만 해줬기에 이 경우는 빼야하는 숫자만큼을 삭제하고 앞에서부터 값을 출력한다

 

정답

def solution(number, k):
    answer = []
    
    # O(N)의 파싱
    for i, num in enumerate(number):
        # 가장 최근 넣은 값 보다 현재값이 크면 빼기, 빼야되는 수가 남아있으면
        while len(answer) > 0 and answer[-1] < num and k > 0 :
            answer.pop()
            k-=1 # 빼야되는 수 감소
        
        # 더이상 뺄게 없으면 남은 거 전부 추가
        if k == 0:
            answer += number[i:]
            break
            
        answer.append(num) # 추가
    
    # 만약 빼지 못했으면 삭제하기
    if k > 0 :
        answer = answer[:-k]
    
    return ''.join(answer)

---

오답

시간복잡도 O(n^2) + 파이썬처럼 짜지 못한 코드 

그래서 시간복잡도를 신경써야하는 테스트 케이스 문제들에 대해서 통과하지 못했다.

def solution(number, k):
    answer = ''
    i = 0
    max_idx = -1 # 범위 내 최대 위치
    max_chr = '0' # 범위 내 최대 값
    
    while(len(answer) < len(number)-k):
        i = max_idx + 1 # 시작점 갱신
        max_chr = '0'
          
        # 만들어야 되는 길이 - 만들었던 길이 = 만들어야 하는 길이
        # len(number)- k - len(answer)  - 1
        # 전체 길이  - 만들어야 하는 길이 = 최대 탐색 가능한 범위
        # len(number) - (len(number)- k - len(answer)  - 1)
        
        # 만들어야 하는 길이 == 남은 길이 일 경우 그만
        print(len(number)- k - len(answer) , len(number) - i)
        if len(number)- k - len(answer)  == len(number) - i:
            for k in range(i,len(number)):
                answer+=number[k]
            break
            
        
        # 전체 탐색
        for j in range(i, len(answer) + k + 1):
    
            # 최대값 갱신
            if int(max_chr) < int(number[j]) :
                max_idx = j
                max_chr = number[j]
        
        answer += max_chr # 문자열 붙이기
        
    return answer